Abstract | ||
---|---|---|
This paper deals with the problem of adding edges to a graph such that the resulting graph becomes an interval graph. The set of edges added is called an augmentation. An algorithm is presented to find a minimal augmentation which runs in a time proportional to the product of the number of vertices and the number of edges of the resulting graph. |
Year | DOI | Venue |
---|---|---|
1981 | 10.1016/0022-0000(81)90022-2 | Journal of Computer and System Sciences |
Keywords | Field | DocType |
interval graph | Discrete mathematics,Strength of a graph,Combinatorics,Line graph,Cycle graph,Mixed graph,Null graph,Butterfly graph,Multiple edges,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
22 | 1 | 0022-0000 |
Citations | PageRank | References |
8 | 6.02 | 5 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tatsuo Ohtsuki | 1 | 194 | 51.39 |
Hajimu Mori | 2 | 10 | 6.96 |
Toshinobu Kashiwabara | 3 | 106 | 16.79 |
Toshio Fujisawa | 4 | 92 | 15.13 |