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