Triangulating graphs with few \(P_4\)'s
From MaRDI portal
Publication:1281383
DOI10.1016/S0166-218X(98)00115-2zbMath0927.68062MaRDI QIDQ1281383
Publication date: 29 November 1999
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
The maker-breaker largest connected subgraph game ⋮ Recognition and isomorphism of tree-like \(P_4\)-connected graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Complement reducible graphs
- On a unique tree representation for \(P_ 4\)-extendible graphs
- A tree representation for \(P_ 4\)-sparse graphs
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- Treewidth. Computations and approximations
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- On the structure of graphs with few \(P_4\)s
- Hamiltonicity in graphs with few \(P_ 4\)'s
- Linear time optimization algorithms for \(P_ 4\)-sparse graphs
- Triangulating graphs without asteroidal triples
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- A Linear Recognition Algorithm for Cographs
- Complexity of Finding Embeddings in a k-Tree
- Computing the Minimum Fill-In is NP-Complete
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- The Pathwidth and Treewidth of Cographs
- P-Components and the Homogeneous Decomposition of Graphs
