Efficient algorithms for Eulerian extension and rural Postman
DOI10.1137/110834810zbMATH Open1267.05131OpenAlexW1974848406MaRDI QIDQ5300482FDOQ5300482
Hannes Moser, Mathias Weller, Rolf Niedermeier, Frederic Dorn
Publication date: 27 June 2013
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/110834810
Recommendations
- Efficient algorithms for Eulerian extension
- A new view on rural postman based on Eulerian extension and matching
- A new view on rural postman based on Eulerian extension and matching
- From few components to an Eulerian graph by adding ARCS
- Rural postman parameterized by the number of components of required edges
schedulingfixed-parameter tractabilityarc routinggraph modificationChinese Postmanmultigraph modification
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Eulerian and Hamiltonian graphs (05C45)
Cited In (19)
- Completing Partial Schedules for Open Shop with Unit Processing Times and Routing
- Domino sequencing: scheduling with state-based sequence-dependent setup times
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- A new view on rural postman based on Eulerian extension and matching
- An updated annotated bibliography on arc routing problems
- On approximate data reduction for the Rural Postman Problem: Theory and experiments
- A survey of parameterized algorithms and the complexity of edge modification
- Switches in Eulerian graphs
- Plane augmentation of plane graphs to meet parity constraints
- Using shortcut edges to maximize the number of triangles in graphs
- Edge constrained Eulerian extensions
- Finding even subgraphs even faster
- Parameterized complexity of \(k\)-Chinese postman problem
- On \((1+\varepsilon)\)-approximate data reduction for the Rural Postman problem
- Efficient algorithms for Eulerian extension
- Editing to Eulerian graphs
- Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
This page was built for publication: Efficient algorithms for Eulerian extension and rural Postman
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300482)
