Recognizing clique graphs of directed and rooted path graphs

DOI10.1016/S0166-218X(99)00028-1zbMath0927.05071MaRDI QIDQ1293208

Jayme Luiz Szwarcfiter, Erich Prisner

Publication date: 5 December 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

characterizationspolynomial time algorithmsclique graphspath graphsstrongly chordal graphs

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

On basic chordal graphs and some of its subclasses ⋮ Split clique graph complexity ⋮ Biclique graphs of interval bigraphs ⋮ Recognizing Helly edge-path-tree graphs and their clique graphs ⋮ The complexity of clique graph recognition ⋮ Unnamed Item ⋮ Recognizing clique graphs of directed edge path graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Clique graphs and Helly graphs
• Matrix multiplication via arithmetic progressions
• Intersection graphs of paths in a tree
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A characterisation of rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Über iterierte Clique-Graphen
• A New Algorithm for Generating All the Maximal Independent Sets
• Dually Chordal Graphs
• Clique Graphs of Chordal and Path Graphs

This page was built for publication: Recognizing clique graphs of directed and rooted path graphs