1. Exact Algorithms for Intervalizing Coloured Graphs.
- Author
-
Bodlaender, Hans and Rooij, Johan
- Subjects
- *
GRAPH coloring , *GRAPH algorithms , *COMPUTER algorithms , *EXPONENTIAL functions , *SUBGRAPHS , *INTERVAL analysis - Abstract
In the I ntervalizing 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 $2^{\mathcal {O}(n/\log n)}$ time. We also give an $\mathcal {O}^{\ast }(2^{n})$ algorithm for the case that the number of colors is not fixed. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF