A new view on rural postman based on Eulerian extension and matching
From MaRDI portal
Publication:1932348
DOI10.1016/j.jda.2012.04.007zbMath1255.68076OpenAlexW2012760542MaRDI QIDQ1932348
Mathias Weller, Manuel Sorge, René van Bevern, Rolf Niedermeier
Publication date: 18 January 2013
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2012.04.007
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Related Items (12)
Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Parameterized complexity of \(k\)-Chinese postman problem ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems ⋮ Completing Partial Schedules for Open Shop with Unit Processing Times and Routing ⋮ Unnamed Item ⋮ Parameterized complexity of min-power asymmetric connectivity ⋮ Basic Terminology, Notation and Results
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of even/odd subgraph problems
- A survey of models and algorithms for winter road maintenance. IV: Vehicle routing and fleet sizing for plowing and snow disposal
- Solving the hierarchical Chinese postman problem as a rural postman problem.
- A branch-and-cut algorithm for the undirected rural postman problem
- New heuristic algorithms for the windy rural postman problem
- Parametrized complexity theory.
- Parameterized Complexity of Connected Even/Odd Subgraph Problems
- Efficient Algorithms for Eulerian Extension
- Parameterized Complexity of Eulerian Deletion Problems
- From Few Components to an Eulerian Graph by Adding Arcs
- A New View on Rural Postman Based on Eulerian Extension and Matching
- An Eulerian exposition
- An algorithm for the Rural Postman problem on a directed graph
- The spanning subgraphs of eulerian graphs
- On general routing problems
- On general routing problems: Comments
- A fundamental problem in vehicle routing
- Approximation Algorithms for Some Postman Problems
- Matching, Euler tours and the Chinese postman
- Arc Routing Problems, Part II: The Rural Postman Problem
- Parameterized and Exact Computation
This page was built for publication: A new view on rural postman based on Eulerian extension and matching
