Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- 31 August 2004
- journal article
- Published by Elsevier BV in Journal of Algorithms
- Vol. 52 (2), 134-151
- https://doi.org/10.1016/j.jalgor.2003.10.001
Abstract
No abstract availableKeywords
Funding Information
- Deutsche Forschungsgemeinschaft (GACˇ R 201/99/0242, NI 369/1-1,1-2)
- Ministerstvo Školství, Mládeže a Tělovýchovy (LN00A056)
- Norges Forskningsråd (143192/410)
- North Atlantic Treaty Organization
This publication has 14 references indexed in Scilit:
- Polynomial-time approximation schemes for packing and piercing fat objectsJournal of Algorithms, 2003
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric GraphsJournal of Algorithms, 1998
- Separators for sphere-packings and nearest neighbor graphsJournal of the ACM, 1997
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- Unit disk graphsDiscrete Mathematics, 1990
- Algorithms for maximum independent setsJournal of Algorithms, 1986
- On the Problem of Partitioning Planar GraphsSIAM Journal on Algebraic Discrete Methods, 1982
- Applications of a Planar Separator TheoremSIAM Journal on Computing, 1980
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979