Exact algorithms for intervalizing coloured graphs

DOI10.1007/s00224-015-9616-6zbMath1331.05202OpenAlexW2019817768WikidataQ59480234 ScholiaQ59480234MaRDI QIDQ255264

Johan M. M. van Rooij, Hans L. Bodlaender

Publication date: 9 March 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-015-9616-6

zbMATH Keywords

graph algorithmspathwidthinterval graphsexact algorithmsintervalizing coloured graphssubexponential time

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Improved Lower Bounds for Graph Embedding Problems

Cites Work

• Unnamed Item
• Exact exponential algorithms.
• A note on exact algorithms for vertex ordering problems on graphs
• Bounded degree interval sandwich problems
• On the complexity of DNA physical mapping
• On exact algorithms for treewidth
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• A Dynamic Programming Approach to Sequencing Problems
• On the proper intervalization of colored caterpillar trees
• Applications of a Planar Separator Theorem
• Triangulating Vertex-Colored Graphs
• Graph Sandwich Problems
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• STACS 2004
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Algorithms – ESA 2005
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The hardness of intervalizing four colored caterpillars
• On intervalizing \(k\)-colored graphs for DNA physical mapping