On approximate data reduction for the Rural Postman Problem: Theory and experiments

DOI10.1002/NET.21985arXiv1812.10131MaRDI QIDQ6092640

Till Fluschnik, René van Bevern, O. Yu. Tsidulko

Publication date: 23 November 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.10131

zbMATH Keywords

NP-hard problemparameterized complexitycapacitated arc routingEulerian extensionlossy kernelizationabove-guarantee parameterization

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Related Items (1)

Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rural postman parameterized by the number of components of required edges
• Polynomial kernels for weighted problems
• New inapproximability bounds for TSP
• Experiments on data reduction for optimal domination in networks
• A deterministic tabu search algorithm for the capacitated arc routing problem
• The fleet size and mix problem for capacitated arc routing
• An application of simultaneous diophantine approximation in combinatorial optimization
• Eulerian graphs and related topics. Part 1, Volume 2
• Parameterized approximation via fidelity preserving transformations
• Constant-factor approximations for capacitated arc routing without triangle inequality
• A new view on rural postman based on Eulerian extension and matching
• On \((1+\varepsilon)\)-approximate data reduction for the Rural Postman problem
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• Revisiting connected vertex cover: FPT algorithms and lossy kernels
• A completeness theory for polynomial (Turing) kernelization
• Computing finest mincut partitions of a graph and application to routing problems
• Parametrized complexity theory.
• Lower and upper bounds for the mixed capacitated arc routing problem
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• Solving the close-enough arc routing problem
• From Few Components to an Eulerian Graph by Adding Arcs
• An Approximation Algorithm for the Capacitated Arc Routing Problem
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Capacitated arc routing problems
• On general routing problems
• A fundamental problem in vehicle routing
• Lossy Kernels for Graph Contraction Problems
• Kernelization
• The laser-plotter beam routing problem
• Matching, Euler tours and the Chinese postman
• Arc Routing Problems, Part II: The Rural Postman Problem
• Eulerian location problems
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• Lossy kernelization
• Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
• Lossy Kernels for Hitting Subgraphs
• Optimal control of plotting and drilling machines: A case study
• Arc Routing
• Bounds for the general capacitated routing problem
• A branch & cut algorithm for the windy general routing problem and special cases
• Efficient Algorithms for Eulerian Extension and Rural Postman
• A cutting plane algorithm for the general routing problem
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem

This page was built for publication: On approximate data reduction for the Rural Postman Problem: Theory and experiments