Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
From MaRDI portal
Publication:1003668
DOI10.1016/j.dam.2007.10.032zbMath1168.05318OpenAlexW2072279239MaRDI QIDQ1003668
Yoshiko Wakabayashi, Cristina G. Fernandes, Orlando Lee
Publication date: 4 March 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.10.032
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (7)
Structural Parameterizations of the Mixed Chinese Postman Problem ⋮ Lane covering with partner bounds in collaborative truckload transportation procurement ⋮ Parameterized complexity of the \(k\)-arc Chinese postman problem ⋮ Postman problems on series-parallel mixed graphs ⋮ Series-parallel graphs are windy postman perfect ⋮ Minimum constellation covers: hardness, approximability and polynomial cases ⋮ The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
Cites Work
- Monadic second-order evaluations on tree-decomposable graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Short cycle covers and the cycle double cover conjecture
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Easy problems for tree-decomposable graphs
- On the complexity of edge traversing
- On the Circuit Cover Problem for Mixed Graphs
- On the Complexity of Finding a Minimum Cycle Cover of a Graph
- Matching, Euler tours and the Chinese postman
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
