Intervalizing k-colored graphs

DOI10.1007/3-540-60084-1_65MaRDI QIDQ4645169zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Babette de Fluiter, Hans L. Bodlaender

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_65

zbMATH Keywords

biconnected componentinput graphinterval graphlinear-time algorithmpath decomposition

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On intervalizing k-colored graphs for DNA physical mapping
• The hardness of intervalizing four colored caterpillars
• Exact algorithms for intervalizing colored graphs
• Exact algorithms for intervalizing coloured graphs
• Precoloring extension. I: Interval graphs

Cites work

• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• On the complexity of DNA physical mapping
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• The complexity of reconstructing trees from qualitative characters and subtrees
• The vertex separation and search number of a graph
• Triangulating 3-Colored Graphs
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• Triangulating Vertex-Colored Graphs
• Two strikes against perfect phylogeny

Cited in

(15)

• Bounded degree interval sandwich problems
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Interval vertex-coloring of a graph with forbidden colors
• Coloring interval graphs with First-Fit
• The balanced connected subgraph problem for geometric intersection graphs
• Exact algorithms for intervalizing coloured graphs
• Coloring k-colorable graphs using smaller palettes
• Interval non-total colorable graphs
• Exact algorithms for intervalizing colored graphs
• SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS
• The Proper Interval Colored Graph problem for caterpillar trees
• On the proper intervalization of colored caterpillar trees
• scientific article; zbMATH DE number 2079419 (Why is no real title available?)
• The hardness of intervalizing four colored caterpillars
• On intervalizing k-colored graphs for DNA physical mapping

This page was built for publication: Intervalizing \(k\)-colored graphs

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