
מירב זהבי
אקדמי בכיר
Parameterized algorithms on geometric intersection graphs
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