Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

DOI10.1016/j.jalgor.2003.10.001zbMath1100.68074OpenAlexW1985758609MaRDI QIDQ4815769

Jochen Alber, Jiří Fiala

Publication date: 8 September 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2003.10.001

zbMATH Keywords

Parameterized complexityIndependent setDisk graphsGraph measureGraph separators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (20)

On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs ⋮ On Embeddability of Unit Disk Graphs onto Straight Lines ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs ⋮ On embeddability of unit disk graphs onto straight lines ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ Maximum matchings in geometric intersection graphs ⋮ Compact and low delay routing labeling scheme for unit disk graphs ⋮ Theory and application of width bounded geometric separators ⋮ Optimality program in segment and string graphs ⋮ Balanced line separators of unit disk graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Reachability oracles for directed transmission graphs ⋮ Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking ⋮ Unnamed Item

This page was built for publication: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs