Abstract | ||
---|---|---|
We describe a polynomial time algorithm to decide for a given connected graph G and a given partition of its vertex set into two sets A and B, whether it is possible to assign a closed interval I(u) to each vertex u of G such that two distinct vertices u and v of G are adjacent if and only if I(u) and I(v) intersect, all intervals assigned to vertices in A have some length L"A, and all intervals assigned to vertices in B have some length L"B where L" |
Year | DOI | Venue |
---|---|---|
2014 | 10.1016/j.ipl.2014.04.002 | Information Processing Letters |
Keywords | Field | DocType |
combinatorial problems,interval graph,graph algorithms,unit interval graph,interval count | Discrete mathematics,Wheel graph,Combinatorics,Vertex (geometry),Bound graph,Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Independent set,Frequency partition of a graph,Mathematics | Journal |
Volume | Issue | ISSN |
114 | 10 | 0020-0190 |
Citations | PageRank | References |
1 | 0.36 | 8 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Felix Joos | 1 | 37 | 11.20 |
Christian Löwenstein | 2 | 131 | 16.28 |
Fabiano de S. Oliveira | 3 | 17 | 4.97 |
Dieter Rautenbach | 4 | 946 | 138.87 |
Jayme Luiz Szwarcfiter | 5 | 618 | 95.79 |