Complexity aspects of the Helly property: graphs and hypergraphs

zbMATH Open1206.05002MaRDI QIDQ1960293FDOQ1960293

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

Recommendations

• The colorful Helly theorem and general hypergraphs
• Complexity aspects of generalized Helly hypergraphs
• The colorful Helly property for hypergraphs
• Publication:4940014
• On the generalized Helly property of hypergraphs, cliques, and bicliques

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)

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
• Title not available (Why is that?)
• On neighborhood-Helly graphs
• The colorful Helly property for hypergraphs
• The complexity of Helly-\(B_1\) EPG graph recognition
• Title not available (Why is that?)
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• The problem of determining the Helly dimension of a graph
• 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)