On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers

DOI10.1137/1.9781611974782.148MaRDI QIDQ4575896zbMATH OpenOpenAlexFDO

Authors Chaya Keller, Gábor Tardos, Shakhar Smorodinsky

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.148

zbMATH Keywords

Hadwiger-Debrunner conjectureintersection graphs of convex sets

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Helly-type theorems and geometric transversal theory (52A35)

Recommendations

• Improved bounds on the Hadwiger-Debrunner numbers
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• scientific article; zbMATH DE number 7662166
• A purely combinatorial proof of the Hadwiger Debrunner \((p,q)\) conjecture
• Homothetic polygons and beyond: maximal cliques in intersection graphs

Cited in

(13)

• Piercing numbers in approval voting
• From a \((p,2)\)-theorem to a tight \((p,q)\)-theorem
• On the chromatic number of disjointness graphs of curves
• The \((2,2)\) and \((4,3)\) properties in families of Fat sets in the plane
• scientific article; zbMATH DE number 7559254 (Why is no real title available?)
• Homothetic polygons and beyond: maximal cliques in intersection graphs
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• Bounds on piercing and line-piercing numbers in families of convex sets in the plane
• Journey to the Center of the Point Set
• Improved bounds on the Hadwiger-Debrunner numbers
• On a problem of Danzer
• On a problem of Danzer

This page was built for publication: On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers

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