Clique-Based Separators for Geometric Intersection Graphs
| Autor: | Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, Leonidas Theocharous |
|---|---|
| Přispěvatelé: | Ahn, Hee-Kap, Sadakane, Kunihiko, Algorithms, EAISI Foundational |
| Rok vydání: | 2021 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Intersection graphs General Computer Science Separator theorems Applied Mathematics Computational geometry intersection graphs separator theorems Theory of computation → Design and analysis of algorithms Computer Science - Computational Geometry Computer Science Applications |
| Zdroj: | 32nd International Symposium on Algorithms and Computation Leibniz International Proceedings in Informatics Leibniz International Proceedings in Informatics (LIPIcs), 212 32nd International Symposium on Algorithms and Computation (ISAAC 2021) Algorithmica, 85(6), 1652-1678. Springer |
| ISSN: | 0178-4617 |
| DOI: | 10.48550/arxiv.2109.09874 |
| Popis: | Let $F$ be a set of $n$ objects in the plane and let $G(F)$ be its intersection graph. A balanced clique-based separator of $G(F)$ is a set $S$ consisting of cliques whose removal partitions $G(F)$ into components of size at most $\delta n$, for some fixed constant $\delta Comment: 23 pages, 8 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink