Efficient Algorithms for Eulerian Extension and Rural Postman

DOI10.1137/110834810zbMath1267.05131MaRDI QIDQ5300482

Rolf Niedermeier, Mathias Weller, Frederic Dorn, Hannes Moser

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

scheduling; arc routing; fixed-parameter tractability; graph modification; Chinese Postman; multigraph modification

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68R05: Combinatorics in computer science

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

05C45: Eulerian and Hamiltonian graphs