Efficient algorithms for Eulerian extension and rural Postman

DOI10.1137/110834810zbMATH Open1267.05131OpenAlexW1974848406MaRDI QIDQ5300482FDOQ5300482

Authors Frederic Dorn, Hannes Moser, Rolf Niedermeier, Mathias Weller 

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

zbMATH Keywords

schedulingfixed-parameter tractabilityarc routinggraph modificationChinese Postmanmultigraph modification

Mathematics Subject Classification ID

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)