מירב זהבי

אקדמי בכיר

Parameterized algorithms on geometric intersection graphs

Jie Xue, Meirav Zehavi

We survey results on the parameterized complexity of various problems on geometric intersection graphs, particularly (unit) disk graphs. Specifically, we consider: (i) vertex-deletion, packing and pattern detection problems; (ii) Independent Set and Dominating Set ; (iii) cut and connectivity problems; (iv) obstacle-removal problems. The discussions include introductions of some of the proof ideas and directions for future research.

שפת פרסום אנגלית
כתב עת Computer Science Review
כרך 58
סטטוס פרסום פורסם - 01.11.2025
100796

Keywords

Disk graph
Geometric intersection graph
Parameterized complexity
Unit disk graph

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science
גישה למסמך
10.1016/j.cosrev.2025.100796
קבצים וקישורים אחרים
Link to publication in Scopus