Parameterized Complexity of Independence and Domination on Geometric Graphs

DOI10.1007/11847250_14MaRDI QIDQ3499733zbMATH OpenOpenAlexFDO

Authors Dániel Marx

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

Mathematics Subject Classification ID

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)

Recommendations

• The parameterized complexity of geometric graph isomorphism
• The parameterized complexity of geometric graph isomorphism
• Mathematical Foundations of Computer Science 2004
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• The complexity of dominating set in geometric intersection graphs
• Independence and domination in polygon graphs
• scientific article; zbMATH DE number 7033848
• Parameterized complexity of independent set in H-free graphs
• Parameterized complexity of generalized domination problems
• Parameterized Complexity of Generalized Domination Problems

Cited in

(34)

• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Optimality of geometric local search
• Parameterized domination in circle graphs
• Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
• Maximum bipartite subgraphs of geometric intersection graphs
• Structure of polynomial-time approximation
• Parameterized computational geometry via decomposition theorems
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• A tight analysis of geometric local search
• Grundy Coloring and friends, half-graphs, bicliques
• The dominating set problem in geometric intersection graphs
• A Purely Democratic Characterization of W[1]
• Parameterized complexity of independent set in H-free graphs
• Approximating dominating set on intersection graphs of rectangles and L-frames
• Parameterized dominating set problem in chordal graphs: Complexity and lower bound
• Dominating set of rectangles intersecting a straight line
• Optimality program in segment and string graphs
• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• On Geometric Set Cover for Orthants
• Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
• Geometric dominating-set and set-cover via local-search
• The homogeneous broadcast problem in narrow and wide strips. I: Algorithms
• The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds
• Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
• W-hierarchies defined by symmetric gates
• Exact multi-covering problems with geometric sets
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• Limits of local search: quality and efficiency
• The complexity of dominating set in geometric intersection graphs
• Domination in Geometric Intersection Graphs
• The parameterized complexity of stabbing rectangles

This page was built for publication: Parameterized Complexity of Independence and Domination on Geometric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499733)