Intersection graphs of vertex disjoint paths in a tree (Q1903730)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Intersection graphs of vertex disjoint paths in a tree |
scientific article; zbMATH DE number 825352
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Intersection graphs of vertex disjoint paths in a tree |
scientific article; zbMATH DE number 825352 |
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
