The hardness of intervalizing four colored caterpillars

DOI10.1016/S0012-365X(00)00257-0zbMath0977.05055MaRDI QIDQ5937916

Carme Àlvarez, Josep Diaz, Maria J. Serna

Publication date: 18 July 2001

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-complete; caterpillar tree; DNA physical mapping; interval graph; intervalizing colored graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92D20: Protein sequences, DNA sequences

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The b-chromatic number of power graphs of complete caterpillars, The Proper Interval Colored Graph problem for caterpillar trees, On the proper intervalization of colored caterpillar trees