Efficient algorithms for Eulerian extension

DOI10.1007/978-3-642-16926-7_11MaRDI QIDQ3057616zbMATH OpenOpenAlexFDO

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

Publication date 16 November 2010

Published in Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16926-7_11

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Efficient algorithms for Eulerian extension and rural Postman
• From few components to an Eulerian graph by adding ARCS
• A new view on rural postman based on Eulerian extension and matching
• A new view on rural postman based on Eulerian extension and matching
• Parameterized complexity of Eulerian deletion problems

Cites work

• An Eulerian exposition
• Approximation Algorithms for Some Postman Problems
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Arc Routing Problems, Part II: The Rural Postman Problem
• Complexity classification of some edge modification problems
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• NP-completeness results for edge modification problems
• On general routing problems
• On general routing problems: Comments
• On Making Directed Graphs Transitive
• Reflections on multivariate algorithmics and problem parameterization
• The spanning subgraphs of eulerian graphs
• Towards fully multivariate algorithmics: some new results and directions in parameter ecology

Cited in

(9)

• A new view on rural postman based on Eulerian extension and matching
• Parameterized complexity of Eulerian deletion problems
• Parameterized complexity of Eulerian deletion problems
• From few components to an Eulerian graph by adding ARCS
• A new view on rural postman based on Eulerian extension and matching
• Rural postman parameterized by the number of components of required edges
• Efficient algorithms for Eulerian extension and rural Postman
• An updated annotated bibliography on arc routing problems
• Weighted Eulerian extensions of random graphs

This page was built for publication: Efficient algorithms for Eulerian extension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057616)