Faster recognition of clique-Helly and hereditary clique-Helly graphs

DOI10.1016/J.IPL.2007.02.017MaRDI QIDQ2379939zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Jayme L. Szwarcfiter

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.02.017

zbMATH Keywords

algorithmsHelly propertyclique-Helly graphsdisk-Helly graphshereditary clique-Helly graphshereditary disk-Helly graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• scientific article; zbMATH DE number 1409177
• Improved algorithms for recognizing \(p\)-Helly and hereditary \(p\)-Helly hypergraphs
• Graph-Theoretic Concepts in Computer Science
• Characterization and recognition of generalized clique-Helly graphs
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• scientific article; zbMATH DE number 553916
• Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration
• Recognizing Helly edge-path-tree graphs and their clique graphs
• A note on the speed of hereditary graph properties
• Clique-width and the speed of hereditary properties

Cites work

• scientific article; zbMATH DE number 5158490 (Why is no real title available?)
• scientific article; zbMATH DE number 22656 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• scientific article; zbMATH DE number 1409177 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• A characterization of clique graphs
• A hierarchy of self-clique graphs
• A partial characterization of clique graphs
• A polynomial algorithm for the strong Helly property
• Clique graphs and Helly graphs
• Dismantling absolute retracts of reflexive graphs
• Graph Classes: A Survey
• Self‐clique graphs and matrix permutations
• Vertex-to-vertex pursuit in a graph
• Über iterierte Clique-Graphen

Cited in

(24)

• Characterization and recognition of generalized clique-Helly graphs
• On the clique behavior and Hellyness of the complements of regular graphs
• On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
• On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• scientific article; zbMATH DE number 1409177 (Why is no real title available?)
• Clique planar graphs
• Biclique-Helly graphs
• On the generalized Helly property of hypergraphs, cliques, and bicliques
• A story of diameter, radius, and (almost) Helly property
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• Cliques and extended triangles. A necessary condition for planar clique graphs
• On edge-sets of bicliques in graphs
• Two infinite families of critical clique-Helly graphs
• Recognizing Helly edge-path-tree graphs and their clique graphs
• The chromatic gap and its extremes
• Helly-gap of a graph and vertex eccentricities
• On neighborhood-Helly graphs
• Improved algorithms for recognizing \(p\)-Helly and hereditary \(p\)-Helly hypergraphs
• Beyond Helly graphs: the diameter problem on absolute retracts
• Distance problems within Helly graphs and \(k\)-Helly graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• On hereditary Helly classes of graphs
• On minimal forbidden subgraph characterizations of balanced graphs

This page was built for publication: Faster recognition of clique-Helly and hereditary clique-Helly graphs

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