Efficient algorithms for Eulerian extension and rural Postman
From MaRDI portal
Publication:5300482
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)
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
Cited in
(22)- Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
- Editing to Eulerian graphs
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- Domino sequencing: scheduling with state-based sequence-dependent setup times
- Parameterized complexity of \(k\)-Chinese postman problem
- Efficient algorithms for Eulerian extension
- On \((1+\varepsilon)\)-approximate data reduction for the Rural Postman problem
- A new view on rural postman based on Eulerian extension and matching
- From few components to an Eulerian graph by adding ARCS
- A new view on rural postman based on Eulerian extension and matching
- Plane augmentation of plane graphs to meet parity constraints
- An updated annotated bibliography on arc routing problems
- Switches in Eulerian graphs
- On approximate data reduction for the Rural Postman Problem: Theory and experiments
- Finding even subgraphs even faster
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- Parameterized directed \(k\)-Chinese postman problem and \(k\) arc-disjoint cycles problem on Euler digraphs
- Edge constrained Eulerian extensions
- Using shortcut edges to maximize the number of triangles in graphs
- Completing partial schedules for open shop with unit processing times and routing
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)