Name
Abstract | ||
|---|---|---|
Let S be a family of arcs on a circle. A graph G = (V,E) is called a circular-arc overlap graph for S if (i) there is a one-to-one correspondence between V and S and (ii) two vertices in V are adjacent if and only if the corresponding arcs in S intersect but neither one of them contains the other. In this article, we present two polynomial time algorithms on circular-arc overlap graphs. Given a circular-arc overlap graph in the form of a family of n arcs, the first algorithm obtains a maximum independent set in O(n2) time and the second one finds a maximum clique in O(n5) time. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1002/net.3230210205 | NETWORKS |
Field | DocType | Volume |
Block graph,Discrete mathematics,Combinatorics,Forbidden graph characterization,Interval graph,Circle graph,Algorithm,Independent set,1-planar graph,Mathematics,Complement graph,Split graph | Journal | 21 |
Issue | ISSN | Citations |
2 | 0028-3045 | 5 |
PageRank | References | Authors |
0.51 | 8 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshinobu Kashiwabara | 1 | 106 | 16.79 |
| Sumio Masuda | 2 | 150 | 20.26 |
| Kazuo Nakajima | 3 | 40 | 6.09 |
| Toshio Fujisawa | 4 | 92 | 15.13 |