Exact algorithms for intervalizing coloured graphs

H. L. Bodlaender, J. M. M. van Rooij

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
94 Downloads (Pure)

Abstract

In the Intervalizing Coloured Graphs problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses (Formula Presented.) time. We also give an (Formula Presented.) algorithm for the case that the number of colors is not fixed.

Original languageEnglish
Pages (from-to)273-286
Number of pages14
JournalTheory of Computing Systems
Volume58
Issue number2
DOIs
Publication statusPublished - 1 Feb 2016

Keywords

  • Exact algorithms
  • Graph algorithms
  • Interval graphs
  • Intervalizing coloured graphs
  • Pathwidth
  • Subexponential time

Fingerprint Dive into the research topics of 'Exact algorithms for intervalizing coloured graphs'. Together they form a unique fingerprint.

Cite this