New Branchwidth Territories | SpringerLink
Skip to main content
Springer Nature Link
Log in

New Branchwidth Territories

  • Conference paper
  • First Online:
STACS 99 (STACS 1999)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1563))

Included in the following conference series:

Abstract

We give an algorithm computing the branchwidth of interval graphs in time O(n 3 log n). This method generalizes to permutation graphs and, more generaly, to trapezoid graphs. In contrast, we show that computing branchwidth is NP-complete for splitgraphs and bipartite graphs.

The first author acknowledges support of DIMATIA Charles University, where he held a visiting position in 1997/8.

The second author acknowledges partial support of Czech Research grants GAČR. 201/1996/0194 and GAUK 1996/194.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bodlaender, H. and D. M. Thilikos, Constructive linear time algorithms for branch-width, Proceedings ICALP’97, Springer-Verlag, LNCS 1256, (1997), pp. 627–637.

    Google Scholar 

  2. Booth, K. and G. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity testing using PQ-tree algorithms, J. of Computer and System Sciences 13, (1976), pp. 335–379.

    MATH  MathSciNet  Google Scholar 

  3. Garey, M.R. and D. S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, Freeman, San Francisco 1979.

    MATH  Google Scholar 

  4. Kloks, T., Treewidth-Computations and Approximations, Springer-Verlag, LNCS 842, 1994.

    MATH  Google Scholar 

  5. Robertson, N. and P.D. Seymour, Graph minors X: Obstructions to tree-decomposition, Journal of Combinatorial Theory, Series B 52, (1991), pp. 153–190.

    Article  MATH  MathSciNet  Google Scholar 

  6. Seymour, P.D. and R. Thomas, Call routing and the ratcatcher, Combinatorica 14, (1994), pp. 217–241.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Vrije Universiteit, 1081 HV, Amsterdam, The Netherlands

    Ton Kloks

  2. Department of Applied Mathematics and DIMATIA, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic

    Jan Kratochvíl

  3. Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität Jena, 07740, Jena, Germany

    Haiko Müller

Authors
  1. Ton Kloks
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan Kratochvíl
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Haiko Müller
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. FB IV - Informatik, Universität Trier, D-54286, Trier, Germany

    Christoph Meinel

  2. LIFL, Université de Lille I, Bătiment 3, F-59655, Villeneuve d’Ascq Cedex, France

    Sophie Tison

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kloks, T., Kratochvíl, J., Müller, H. (1999). New Branchwidth Territories. In: Meinel, C., Tison, S. (eds) STACS 99. STACS 1999. Lecture Notes in Computer Science, vol 1563. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49116-3_16

Download citation

  • DOI: https://doi.org/10.1007/3-540-49116-3_16

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-65691-3

  • Online ISBN: 978-3-540-49116-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation