Efficient Algorithms for Eulerian Extension

DOI10.1007/978-3-642-16926-7_11zbMath1309.68080OpenAlexW1788536844MaRDI QIDQ3057616

Rolf Niedermeier, Hannes Moser, Mathias Weller, Frederic Dorn

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

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

Related Items (5)

Rural postman parameterized by the number of components of required edges ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• NP-completeness results for edge modification problems
• Reflections on Multivariate Algorithmics and Problem Parameterization
• On Making Directed Graphs Transitive
• An Eulerian exposition
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• The spanning subgraphs of eulerian graphs
• On general routing problems
• On general routing problems: Comments
• 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

This page was built for publication: Efficient Algorithms for Eulerian Extension