Complexity aspects of the Helly property: graphs and hypergraphs

MaRDI QIDQ1960293zbMATH OpenFDO

Authors Mitre C. Dourado, Fábio Protti, Jayme L. Szwarcfiter

Publication date 13 October 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/222810, http://www.emis.de/journals/EJC/Surveys/index.html

zbMATH Keywords

computational complexityHelly propertyNP-completeNP-hardrecognition algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Helly-type theorems and geometric transversal theory (52A35)

Recommendations

• The colorful Helly theorem and general hypergraphs
• Complexity aspects of generalized Helly hypergraphs
• The colorful Helly property for hypergraphs
• scientific article; zbMATH DE number 1409177
• On the generalized Helly property of hypergraphs, cliques, and bicliques

Cited in

(21)

• Split clique graph complexity
• On the clique behavior and Hellyness of the complements of regular graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• The Helly property on subfamilies of limited size
• The Helly property and satisfiability of Boolean formulas defined on set families
• Characterization of classical graph classes by weighted clique graphs
• On the generalized Helly property of hypergraphs, cliques, and bicliques
• A story of diameter, radius, and (almost) Helly property
• On the computational complexity of the Helly number in the \(P_3\) and related convexities
• Domination in digraphs and their direct and Cartesian products
• A unified approach to recognize squares of split graphs
• scientific article; zbMATH DE number 5064049 (Why is no real title available?)
• On neighborhood-Helly graphs
• The colorful Helly property for hypergraphs
• The complexity of Helly-\(B_1\) EPG graph recognition
• scientific article; zbMATH DE number 4101253 (Why is no real title available?)
• The problem of determining the Helly dimension of a graph
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• The colorful Helly theorem and general hypergraphs
• On the Helly property working as a compactness criterion on graphs
• Helly's property for \(n\)-cliques and the degree of a graph

This page was built for publication: Complexity aspects of the Helly property: graphs and hypergraphs

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