Exact algorithms for intervalizing coloured graphs

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

doi:10.1007/s00224-015-9616-6

Exact algorithms for intervalizing coloured graphs

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

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

1 Citation (Scopus)

134 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 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

art%3A10.1007%2Fs00224-015-9616-6Final published version, 219 KB

Cite this

@article{96e51a16fa8145ad933bb7b080821a6a,

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, {H. L.} and {van Rooij}, {J. 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",

number = "2",

}

TY - JOUR

T1 - Exact algorithms for intervalizing coloured graphs

AU - Bodlaender, H. L.

AU - van Rooij, J. 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

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

Other files and links

Fingerprint

Cite this