Intersection graphs of vertex disjoint paths in a tree (Q1903730)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Intersection graphs of vertex disjoint paths in a tree |
scientific article |
Statements
Intersection graphs of vertex disjoint paths in a tree (English)
0 references
23 April 1996
0 references
The paper characterizes the intersection graphs of internally vertex disjoint path in a tree in terms of maximal clique separators and by forbidden subgraphs and presents an algorithm recognizing these graphs in time \(O(n^4m)\).
0 references
intersection graphs
0 references
path
0 references
tree
0 references
clique separators
0 references
algorithm
0 references
0 references
