scientific article; zbMATH DE number 17505

MaRDI QIDQ3974827zbMATH OpenFDO

Authors Shaohan Ma, Julin Wu

Publication date 26 June 1992

zbMATH Keywords

algorithmminimal relative separatorsseparator hypergraphstrongly chordal graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

[For the entire collection see Zbl 0726.00009.] We characterize strongly chordal graphs by minimal relative separators. We show that a graph \(G\) is strongly chordal if and only if \(G\) is chordal and the minimal relative separator hypergraph of \(G\) is totally balanced. An algorithm to find all the minimal relative separators of a chordal graph is also given.

Recommendations

• Minimal relative separators of chordal graphs
• A characterization of strongly chordal graphs
• Minimal weak separators of chordal graphs.
• A new characterization of strongly chordal graphs
• Minimal vertex separators of chordal graphs

Cited in

(7)

• A characterization of strongly chordal graphs
• Minimal vertex separators and new characterizations for dually chordal graphs
• Minimal weak separators of chordal graphs.
• Minimal relative separators of chordal graphs
• Characterizing and computing the structure of clique intersections in strongly chordal graphs
• Strong clique trees, neighborhood trees, and strongly chordal graphs
• Graphs that have separator tree representations

This page was built for publication:

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