k-separator chordal graphs: leafage and subfamilies

DOI10.1111/J.1475-3995.2012.00875.XMaRDI QIDQ2862158zbMATH OpenOpenAlexFDO

Authors Paulo Renato Da Costa Pereira, Lilian Markenzon, Christina F. E. M. 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

\(k\)-caterpillar\(k\)-sep chordal graphchordal graphleafageminimal vertex separator

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• The leafage of a chordal graph
• Minimal vertex separators of chordal graphs
• On k-trees with given leafages
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• The vertex leafage of chordal graphs

Cites work

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

Cited in

(10)

• The vertex leafage of chordal graphs
• Linear algorithms for chordal graphs of bounded directed vertex leafage
• Non-separating cliques, asteroidal number and leafage. The minimal 4-asteroidal split graphs
• Strictly interval graphs: characterization and linear time recognition
• Clique trees of chordal graphs: leafage and 3-asteroidals
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• The leafage of a chordal graph
• Graphs that have separator tree representations
• On k-trees with given leafages
• The Neighborhood Polynomial of Chordal Graphs

This page was built for publication: \(k\)-separator chordal graphs: leafage and subfamilies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2862158)