Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Constrained-Path Labellings on Graphs of Bounded Clique-Width

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

Given a graph G we consider the problem of preprocessing it so that given two vertices x,y and a set X of vertices, we can efficiently report the shortest path (or just its length) between x,y that avoids X. We attach labels to vertices in such a way that this length can be determined from the labels of x,y and the vertices X. For a graph with n vertices of tree-width or clique-width k, we construct labels of size O(k 2log 2 n). The constructions extend to directed graphs. The problem is motivated by routing in networks in case of failures or of routing policies which forbid certain paths.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bodlaender, H.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  2. Courcelle, B.: The monadic second-order logic of graphs xv: on a conjecture by D. Seese. J. Appl. Log. 4, 79–114 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  3. Courcelle, B., Kanté, M.: Graph operations characterizing rank-width and balanced graph expressions. In: Kratsch, D., Brandstädt, A., Müller, H. (eds.) Proceedings of the 33rd International Workshop on Graphs (WG07). Lecture Notes in Computer Science, vol. 4769, pp. 66–75. Springer, Berlin (2007)

    Google Scholar 

  4. Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1–3), 77–114 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  5. Courcelle, B., Twigg, A.: Compact forbidden-set routing. In: Thomas, W., Weil, P. (eds.) 24th International Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 4393, pp. 37–48. Springer, Berlin (2007)

    Google Scholar 

  6. Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique-width. Discrete Appl. Math. 131(1), 129–150 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  7. Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125–150 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  8. Courcelle, B., Gavoille, C., Kanté, M., Twigg, A.: Connectivity check in 3-connected planar graphs with obstacles. Electron. Notes Discrete Math. 31, 151–155 (2008)

    Article  Google Scholar 

  9. Fellows, M., Rosamond, F., Rotics, U., Szeider, S.: Clique-width minimization is NP-hard. In: STOC 2006: Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, pp. 354–362. ACM, New York (2006)

    Chapter  Google Scholar 

  10. Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distributed Comput. 16(2–3), 111–120 (2003)

    Article  Google Scholar 

  11. Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85–112 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  12. Gupta, A., Kumar, A., Thorup, M.: Tree based mpls routing. In: SPAA ’03: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 193–199. ACM, New York (2003)

    Chapter  Google Scholar 

  13. Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596–603 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  14. Oum, S.: Approximating rank-width and clique-width quickly. In: Kratsch, D. (ed.) Proceedings of the 31st International Workshop on Graphs (WG 2005). Lecture Notes in Computer Science, vol. 3787, pp. 49–58. Springer, Berlin (2005)

    Google Scholar 

  15. Wanke, E.: k-nlc graphs and polynomial algorithms. Discrete Appl. Math. 54(2–3), 251–266 (1994)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LaBRI, Institut Universitaire de France and Bordeaux University, 351 Cours de la Liberation, 33405, Talence, France

    Bruno Courcelle

  2. Computing Laboratory, University of Oxford, Oxford, UK

    Andrew Twigg

Authors
  1. Bruno Courcelle
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew Twigg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrew Twigg.

Additional information

B. Courcelle was supported by the GRAAL project of “Agence Nationale pour la Recherche”.

This work was done under the support for A. Twigg by US Army Research Laboratory and UK Ministry of Defence grant W911NF-06-3-0001, and while at the Computer Laboratory, University of Cambridge.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Courcelle, B., Twigg, A. Constrained-Path Labellings on Graphs of Bounded Clique-Width. Theory Comput Syst 47, 531–567 (2010). https://doi.org/10.1007/s00224-009-9211-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-009-9211-9

Keywords

Search

Navigation