Exact Algorithms for Intervalizing Coloured Graphs
Publication date
2016-02-01
Authors
Bodlaender, Hans L.
van Rooij, J.M.M.
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
No license information available
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, Theoretical Computer Science, Computational Theory and Mathematics
Citation
Bodlaender, H L & van Rooij, J M M 2016, 'Exact Algorithms for Intervalizing Coloured Graphs', Theory of Computing Systems, vol. 58, no. 2, pp. 273-286. https://doi.org/10.1007/s00224-015-9616-6