Efficient Algorithms for Eulerian Extension and Rural Postman

DOI10.1137/110834810zbMath1267.05131OpenAlexW1974848406MaRDI QIDQ5300482

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

zbMATH Keywords

schedulingarc routingfixed-parameter tractabilitygraph modificationChinese Postmanmultigraph modification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (13)

Plane augmentation of plane graphs to meet parity constraints ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Finding even subgraphs even faster ⋮ 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 ⋮ Editing to Eulerian graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Completing Partial Schedules for Open Shop with Unit Processing Times and Routing ⋮ Using shortcut edges to maximize the number of triangles in graphs ⋮ Domino sequencing: scheduling with state-based sequence-dependent setup times

This page was built for publication: Efficient Algorithms for Eulerian Extension and Rural Postman