Back to Search
Start Over
NP-Completeness of Interval Graph Completion from a Path Graph.
- Source :
-
Electronics & Communications in Japan, Part 3: Fundamental Electronic Science . Jun95, Vol. 78 Issue 6, p95-102. 8p. - Publication Year :
- 1995
-
Abstract
- Given a set of paths on a tree, the graph with vertices corresponding to the paths, where the corresponding vertices are connected by an edge when two paths intersect, is called the path graph. Given a set A of finite intervals on a straight line, the graph with vertices corresponding to the intervals belonging to A, where an edge is provided when two intervals intersect, is called the interval graph. In this paper, it is shown that the problem to decide whether or not a given path graph can be converted to an interval graph by adding K or less edges is NP-complete. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10420967
- Volume :
- 78
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- Electronics & Communications in Japan, Part 3: Fundamental Electronic Science
- Publication Type :
- Academic Journal
- Accession number :
- 13723550
- Full Text :
- https://doi.org/10.1002/ecjc.4430780610