تقرير
Finding a Maximum Clique in a Grounded 1-Bend String Graph
| العنوان: | Finding a Maximum Clique in a Grounded 1-Bend String Graph |
|---|---|
| المؤلفون: | Keil, J. Mark, Mondal, Debajyoti, Moradi, Ehsan, Nekrich, Yakov |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computational Geometry, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, 68Q25, 65D18, I.3.5 |
| الوصف: | A grounded 1-bend string graph is an intersection graph of a set of polygonal lines, each with one bend, such that the lines lie above a common horizontal line $\ell$ and have exactly one endpoint on $\ell$. We show that the problem of finding a maximum clique in a grounded 1-bend string graph is APX-hard, even for strictly $y$-monotone strings. For general 1-bend strings, the problem remains APX-hard even if we restrict the position of the bends and end-points to lie on at most three parallel horizontal lines. We give fast algorithms to compute a maximum clique for different subclasses of grounded segment graphs, which are formed by restricting the strings to various forms of $L$-shapes. Comment: A preliminary version of the paper was presented at the 32nd Canadian Conference on Computational Geometry (CCCG 2020) |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2107.05198 |
| رقم الأكسشن: | edsarx.2107.05198 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |