Name
Abstract | ||
|---|---|---|
We consider the problem of finding interval graph representations that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir (1997 25) proved that the problem is NP -complete if only the former are given. For the case when both are given, Fulkerson and Gross (1965 8) gave an O ( n 2 ) time algorithm; we improve this to O ( n + m ) time and supplement it with a logspace algorithm. For the case when only the latter are given, we give both an O ( n m ) time algorithm and a logspace algorithm. In all these bounds, n is the number of vertices and m is the number of edges in the input graph.Complementing their hardness result, Pe'er and Shamir give a polynomial-time algorithm for the case that the input graph has a unique interval ordering of its maximal cliques. For such graphs, their algorithm computes an interval representation (if it exists) that respects a given set of distance inequalities between the interval endpoints. We observe that deciding if such a representation exists is NL -complete. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jda.2015.05.011 | Journal of Discrete Algorithms |
Keywords | DocType | Volume |
Constrained graph representation,Intersection graph,Interval graph,Linear time,Logspace | Conference | 34 |
Issue | ISSN | Citations |
C | 1570-8667 | 2 |
PageRank | References | Authors |
0.38 | 24 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Köbler | 1 | 580 | 46.51 |
| Sebastian Kuhnert | 2 | 36 | 6.52 |
| Osamu Watanabe | 3 | 960 | 104.55 |