Efficient algorithms for Eulerian extension and rural Postman

DOI10.1137/110834810MaRDI QIDQ5300482zbMATH OpenOpenAlexFDO

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)

• 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
• Completing partial schedules for open shop with unit processing times and routing
• 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
• From few components to an Eulerian graph by adding ARCS
• Editing to Eulerian graphs
• A new view on rural postman based on Eulerian extension and matching
• Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
• Parameterized directed \(k\)-Chinese postman problem and \(k\) arc-disjoint cycles problem on Euler digraphs

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)