Exact algorithms for intervalizing coloured graphs

DOI10.1007/S00224-015-9616-6zbMATH Open1331.05202OpenAlexW2019817768WikidataQ59480234 ScholiaQ59480234MaRDI QIDQ255264FDOQ255264

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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• 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
• Exact exponential algorithms.
• A note on exact algorithms for vertex ordering problems on graphs

Cited In (6)

• Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
• Complexity of tree-coloring interval graphs equitably
• Improved Lower Bounds for Graph Embedding Problems
• Template-driven rainbow coloring of proper interval graphs
• An optimal greedy heuristic to color interval graphs
• Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles

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)