Parameterized Complexity of Independence and Domination on Geometric Graphs
From MaRDI portal
Publication:3499733
DOI10.1007/11847250_14zbMath1154.68431OpenAlexW1575166720MaRDI QIDQ3499733
Publication date: 3 June 2008
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11847250_14
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (31)
Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds ⋮ A Purely Democratic Characterization of W[1] ⋮ Geometric dominating-set and set-cover via local-search ⋮ The parameterized complexity of stabbing rectangles ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Parameterized domination in circle graphs ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ The complexity of dominating set in geometric intersection graphs ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Domination When the Stars Are Out ⋮ Limits of local search: quality and efficiency ⋮ Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy ⋮ Structure of polynomial-time approximation ⋮ W-hierarchies defined by symmetric gates ⋮ Dominating set of rectangles intersecting a straight line ⋮ Parameterized Complexity of Stabbing Rectangles and Squares in the Plane ⋮ Optimality program in segment and string graphs ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ Domination in Geometric Intersection Graphs ⋮ Unnamed Item ⋮ On Geometric Set Cover for Orthants ⋮ Unnamed Item ⋮ Exact multi-covering problems with geometric sets ⋮ The Dominating Set Problem in Geometric Intersection Graphs ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ A tight analysis of geometric local search
This page was built for publication: Parameterized Complexity of Independence and Domination on Geometric Graphs
