Exact Algorithms for Intervalizing Coloured Graphs

Hans L. Bodlaender; Johan M M van Rooij

doi:10.1007/s00224-015-9616-6

Exact Algorithms for Intervalizing Coloured Graphs

Hans L. Bodlaender^*, Johan M M van Rooij

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

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 language	English
Pages (from-to)	273-286
Number of pages	14
Journal	Theory of Computing Systems
Volume	58
Issue number	2
DOIs	https://doi.org/10.1007/s00224-015-9616-6
Publication status	Published - 1 Feb 2016

Keywords

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

Access to Document

10.1007/s00224-015-9616-6

ExactFinal published version, 184 KB

Cite this

@article{bda8faa0198e4ab8880e719ee641910c,

title = "Exact Algorithms for Intervalizing Coloured Graphs",

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.",

keywords = "Exact algorithms, Graph algorithms, Interval graphs, Intervalizing coloured graphs, Pathwidth, Subexponential time",

author = "Bodlaender, {Hans L.} and {van Rooij}, {Johan M M}",

year = "2016",

month = feb,

day = "1",

doi = "10.1007/s00224-015-9616-6",

language = "English",

volume = "58",

pages = "273--286",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Exact Algorithms for Intervalizing Coloured Graphs

AU - Bodlaender, Hans L.

AU - van Rooij, Johan M M

PY - 2016/2/1

Y1 - 2016/2/1

N2 - 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.

AB - 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.

KW - Exact algorithms

KW - Graph algorithms

KW - Interval graphs

KW - Intervalizing coloured graphs

KW - Pathwidth

KW - Subexponential time

UR - http://www.scopus.com/inward/record.url?scp=84954395175&partnerID=8YFLogxK

U2 - 10.1007/s00224-015-9616-6

DO - 10.1007/s00224-015-9616-6

M3 - Article

AN - SCOPUS:84954395175

SN - 1432-4350

VL - 58

SP - 273

EP - 286

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 2

ER -

Exact Algorithms for Intervalizing Coloured Graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this