Minimum-membership geometric dominating set: complexity and algorithms

DOI10.1007/978-981-95-0215-8_17MaRDI QIDQ6867274zbMATH OpenFDO

Authors Bhavya Bansal, Raghunath Reddy Madireddy, Supantha Pandit

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-981-95-0215-8_17

zbMATH Keywords

\textsf{APX}-hard\textsf{NP}-hardgeometric dominating setintervalslinesminimum membership dominating setsegments

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• Approximability and hardness of geometric hitting set with axis-parallel rectangles
• Computing and Combinatorics
• Domination in Geometric Intersection Graphs
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Hardness results and approximation schemes for discrete packing and domination problems
• scientific article; zbMATH DE number 91051 (Why is no real title available?)
• Minimum membership covering and hitting
• Minimum membership hitting sets of axis parallel segments
• Minimum-weight triangulation is NP-hard
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Parameterized complexity of minimum membership dominating set
• Perfect Code is \(W[1]\)-complete
• Perfect codes in Cayley graphs
• Perfect codes in graphs
• Perfect codes over graphs
• Reducibility among combinatorial problems
• The complexity of satisfiability problems
• The Rectilinear Steiner Tree Problem is NP-Complete
• Unit disk graphs

This page was built for publication: Minimum-membership geometric dominating set: complexity and algorithms

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