Recognizing clique graphs of directed and rooted path graphs

DOI10.1016/S0166-218X(99)00028-1zbMATH Open0927.05071MaRDI QIDQ1293208FDOQ1293208

Authors: Erich Prisner, Jayme L. Szwarcfiter 

Publication date: 5 December 1999

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

Recommendations

• Publication:4940014
• Recognizing Helly edge-path-tree graphs and their clique graphs
• The complexity of clique graph recognition
• Recognizing \(k\)-path graphs
• scientific article; zbMATH DE number 2188421
• scientific article; zbMATH DE number 4116571
• Clique Graphs of Chordal and Path Graphs
• scientific article; zbMATH DE number 2096440
• Clique Graph Recognition Is NP-Complete

zbMATH Keywords

characterizationsclique graphspath graphsstrongly chordal graphspolynomial time algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Split clique graph complexity
• Recognizing clique graphs of directed edge path graphs
• Title not available (Why is that?)
• On basic chordal graphs and some of its subclasses
• Title not available (Why is that?)
• Recognizing Helly edge-path-tree graphs and their clique graphs
• The complexity of clique graph recognition
• Biclique graphs of interval bigraphs

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

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