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)

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

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)