k-separator chordal graphs: leafage and subfamilies

DOI10.1111/j.1475-3995.2012.00875.xzbMath1274.90463MaRDI QIDQ2862158

Paulo Renato da Costa Pereira, Lilian Markenzon, Christina Fraga Esteves Maciel Waga

Publication date: 14 November 2013

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/j.1475-3995.2012.00875.x

zbMATH Keywords

chordal graph; minimal vertex separator; leafage; \(k\)-caterpillar; \(k\)-sep chordal graph

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

Related Items

Strictly interval graphs: characterization and linear time recognition

Cites Work

• Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
• Separating subgraphs in k-trees: Cables and caterpillars
• A linear time algorithm to list the minimal separators of chordal graphs
• A clique-difference encoding scheme for labelled \(k\)-path graphs
• Minimal vertex separators of chordal graphs
• Clique tree generalization and new subclasses of chordal graphs
• Algorithmic graph theory and perfect graphs
• Subclasses of \(k\)-trees: characterization and recognition
• Non-separating cliques, asteroidal number and leafage. The minimal 4-asteroidal split graphs
• One-phase algorithm for the determination of minimal vertex separators of chordal graphs
• On double and multiple interval graphs
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• On the tree representation of chordal graphs
• The leafage of a chordal graph