Exact algorithms for intervalizing coloured graphs

DOI10.1007/S00224-015-9616-6MaRDI QIDQ255264zbMATH OpenOpenAlexWikidataFDO

Authors Hans L. Bodlaender, Johan M. M. Van Rooij

Publication date 9 March 2016

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

exact algorithmsgraph algorithmsinterval graphsintervalizing coloured graphspathwidthsubexponential time

Mathematics Subject Classification ID

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

Recommendations

• Exact algorithms for intervalizing colored graphs
• Intervalizing \(k\)-colored graphs
• Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths
• scientific article; zbMATH DE number 1990715
• An optimal greedy heuristic to color interval graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A note on exact algorithms for vertex ordering problems on graphs
• Algorithms – ESA 2005
• Applications of a Planar Separator Theorem
• Bounded degree interval sandwich problems
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Exact exponential algorithms.
• Graph Sandwich Problems
• On exact algorithms for treewidth
• On intervalizing \(k\)-colored graphs for DNA physical mapping
• On the complexity of DNA physical mapping
• On the proper intervalization of colored caterpillar trees
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• STACS 2004
• The hardness of intervalizing four colored caterpillars
• Triangulating Vertex-Colored Graphs

Cited in

(10)

• An optimal greedy heuristic to color interval graphs
• Complexity of tree-coloring interval graphs equitably
• Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
• Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
• Exact algorithms for intervalizing colored graphs
• Exactly hittable interval graphs
• Intervalizing \(k\)-colored graphs
• Improved lower bounds for graph embedding problems
• Template-driven rainbow coloring of proper interval graphs
• A technique for exact computation of precoloring extension on interval graphs

This page was built for publication: Exact algorithms for intervalizing coloured graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q255264)