تقرير
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 |
كن أول من يترك تعليقا!