Geodesic
Finding a Maximum Clique in a Grounded 1-Bend String Graph
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 553-575.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 end point 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.
DOI : 10.7155/jgaa.00608
Keywords: Computational Geometry Intersection Graph, String graph, NP-hard, Dynamic Programming 
@article{JGAA_2022_26_4_a6,
     author = {J. Mark Keil and Debajyoti Mondal and Ehsan Moradi and Yakov Nekrich},
     title = {Finding a {Maximum} {Clique} in a {Grounded} {1-Bend} {String} {Graph}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {553--575},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2022},
     doi = {10.7155/jgaa.00608},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00608/}
}
TY  - JOUR
AU  - J. Mark Keil
AU  - Debajyoti Mondal
AU  - Ehsan Moradi
AU  - Yakov Nekrich
TI  - Finding a Maximum Clique in a Grounded 1-Bend String Graph
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 553
EP  - 575
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00608/
DO  - 10.7155/jgaa.00608
LA  - en
ID  - JGAA_2022_26_4_a6
ER  - 
%0 Journal Article
%A J. Mark Keil
%A Debajyoti Mondal
%A Ehsan Moradi
%A Yakov Nekrich
%T Finding a Maximum Clique in a Grounded 1-Bend String Graph
%J Journal of Graph Algorithms and Applications
%D 2022
%P 553-575
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00608/
%R 10.7155/jgaa.00608
%G en
%F JGAA_2022_26_4_a6
J. Mark Keil; Debajyoti Mondal; Ehsan Moradi; Yakov Nekrich. Finding a Maximum Clique in a Grounded 1-Bend String Graph. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 553-575. doi : 10.7155/jgaa.00608. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00608/

Cité par Sources :