Parameterized Complexity of Independence and Domination on Geometric Graphs

DOI10.1007/11847250_14zbMATH Open1154.68431OpenAlexW1575166720MaRDI QIDQ3499733FDOQ3499733

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

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

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)

Cited In (35)

• Maximum bipartite subgraphs of geometric intersection graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
• Parameterized domination in circle graphs
• Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
• Parameterized computational geometry via decomposition theorems
• Grundy Coloring and friends, half-graphs, bicliques
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• The parameterized complexity of stabbing rectangles
• Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
• W-hierarchies defined by symmetric gates
• The complexity of dominating set in geometric intersection graphs
• A tight analysis of geometric local search
• The dominating set problem in geometric intersection graphs
• Parameterized dominating set problem in chordal graphs: Complexity and lower bound
• Optimality program in segment and string graphs
• Efficient sub-5 approximations for minimum dominating sets in unit disk 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
• Domination when the stars are out
• 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)