Experiments on data reduction for optimal domination in networks

DOI10.1007/S10479-006-0045-4zbMATH Open1106.90011OpenAlexW2157344936MaRDI QIDQ863574FDOQ863574

Authors: Jochen Alber, Nadja Betzler, Rolf Niedermeier 

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

Recommendations

• SOFSEM 2006: Theory and Practice of Computer Science
• Polynomial-time data reduction for dominating set
• scientific article; zbMATH DE number 2089218
• scientific article; zbMATH DE number 2222002
• scientific article; zbMATH DE number 708868

zbMATH Keywords

optimal solutionsdominationnetwork optimizationNP-complete problemexperimental studypreprocessing by data reduction rules

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Cites Work

• Title not available (Why is that?)
• A threshold of ln n for approximating set cover
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Domination in Graphs Applied to Electric Power Networks
• Polynomial-time data reduction for dominating set
• Bidimensionality: new connections between FPT algorithms and PTASs
• A refined search tree technique for dominating set on planar graphs
• Fundamentals of Computation Theory
• STACS 2005
• Experimental analysis of Heuristic algorithms for the dominating set problem
• Title not available (Why is that?)
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS

Cited In (26)

• Kernelization: new upper and lower bound techniques
• A Retrospective on (Meta) Kernelization
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• Data Reduction for Maximum Matching on Real-World Graphs
• Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
• Quadratic kernelization for convex recoloring of trees
• Independent strong weak domination: A mathematical programming approach
• SOFSEM 2006: Theory and Practice of Computer Science
• Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
• Kernelization and complexity results for connectivity augmentation problems
• On approximating (connected) 2-edge dominating set by a tree
• On approximating (connected) 2-edge dominating set by a tree
• Fixed-parameter tractability results for full-degree spanning tree and its dual
• Search-space reduction via essential vertices
• On approximate data reduction for the Rural Postman Problem: Theory and experiments
• Upper bounds for \(\alpha \)-domination parameters
• New analysis and computational study for the planar connected dominating set problem
• Tree decompositions of graphs: saving memory in dynamic programming
• Computational study on planar dominating set problem
• Title not available (Why is that?)
• Reflections on kernelizing and computing unrooted agreement forests
• Dominating complex networks by identifying minimum skeletons
• An experimental study on generating planar graphs
• Independent strong domination in complementary prisms
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• Uncertain weighted dominating set: a prototype application on natural disaster relief management

Uses Software

• LEDA
• BRITE

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

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