Experiments on data reduction for optimal domination in networks

DOI10.1007/s10479-006-0045-4zbMath1106.90011OpenAlexW2157344936MaRDI QIDQ863574

Rolf Niedermeier, Jochen Alber, Nadja Betzler

Publication date: 5 February 2007

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-006-0045-4

zbMATH Keywords

optimal solutionsdominationnetwork optimizationNP-complete problemexperimental studypreprocessing by data reduction rules

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Related Items (21)

Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ A Retrospective on (Meta) Kernelization ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ On approximating (connected) 2-edge dominating set by a tree ⋮ Upper bounds for \(\alpha \)-domination parameters ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space ⋮ Quadratic kernelization for convex recoloring of trees ⋮ An Experimental Study on Generating Planar Graphs ⋮ Tree decompositions of graphs: saving memory in dynamic programming ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Fixed-parameter tractability results for full-degree spanning tree and its dual ⋮ Kernelization and complexity results for connectivity augmentation problems ⋮ Independent strong domination in complementary prisms ⋮ Uncertain weighted dominating set: a prototype application on natural disaster relief management ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Computational study on planar dominating set problem ⋮ Independent strong weak domination: A mathematical programming approach

Uses Software

• LEDA
• BRITE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Experimental analysis of Heuristic algorithms for the dominating set problem
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• A refined search tree technique for dominating set on planar graphs
• A threshold of ln n for approximating set cover
• Polynomial-time data reduction for dominating set
• Domination in Graphs Applied to Electric Power Networks
• Fundamentals of Computation Theory
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
• STACS 2005

This page was built for publication: Experiments on data reduction for optimal domination in networks