Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
From MaRDI portal
Publication:4815769
DOI10.1016/j.jalgor.2003.10.001zbMath1100.68074MaRDI QIDQ4815769
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
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
On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk 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, What’s Next? Future Directions in Parameterized Complexity, Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs, Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams