Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way
From MaRDI portal
Publication:3010409
DOI10.1007/978-3-642-20877-5_29zbMath1333.05284MaRDI QIDQ3010409
Publication date: 1 July 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_29
distance-hereditary graphs; stretch number; graph algorithms; recognition problem; split decomposition
05C75: Structural characterization of families of graphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Cites Work
- Unnamed Item
- Networks with small stretch number
- Completely separable graphs
- Solving some NP-complete problems using split decomposition
- Clique-width of graphs defined by one-vertex extensions
- Distance-hereditary graphs
- On the extension of bipartite to parity graphs
- Graph classes between parity and distance-hereditary graphs
- Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way
- Decomposition of Directed Graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- Recognizing circle graphs in polynomial time
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Graphs with bounded induced distance
- Compact-port routing models and applications to distance-hereditary graphs