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

DOI10.1016/j.jalgor.2003.10.001zbMath1100.68074MaRDI 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 complexity; Independent set; Disk graphs; Graph measure; Graph separators

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Unnamed Item, Unnamed Item, On Embeddability of Unit Disk Graphs onto Straight Lines, Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking, On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs, Unnamed Item, Optimality program in segment and string graphs, Balanced line separators of 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, Parameterized dominating set problem in chordal graphs: Complexity and lower bound, Subexponential algorithms for variants of the homomorphism problem in string graphs, Reachability oracles for directed transmission graphs, What’s Next? Future Directions in Parameterized Complexity, Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams