The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth

DOI10.1137/15M1034337zbMath1351.05100OpenAlexW2557667247MaRDI QIDQ2835842

No author found.

Publication date: 30 November 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1034337

zbMATH Keywords

pathwidthmixed graphsChinese Postmantreedepth

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Signed and weighted graphs (05C22)

Related Items (15)

Length-bounded cuts: proper interval graphs and structural parameters ⋮ Parameterized Algorithms for Queue Layouts ⋮ An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times ⋮ A heuristic approach to the treedepth decomposition problem for large graphs ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Unnamed Item ⋮ Parameterized algorithms for book embedding problems ⋮ Parameterized Algorithms for Book Embedding Problems ⋮ On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering ⋮ On fixed-order book thickness parameterized by the pathwidth of the vertex ordering ⋮ The parameterized complexity of the minimum shared edges problem ⋮ Parameterized Algorithms for Queue Layouts ⋮ Fine-grained parameterized complexity analysis of graph coloring problems

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Parameterized complexity of generalized domination problems
• On the complexity of some colorful problems parameterized by treewidth
• Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
• Treewidth. Computations and approximations
• Parametrized complexity theory.
• Parameterized Complexity of the k-Arc Chinese Postman Problem
• Structural Parameterizations of the Mixed Chinese Postman Problem
• Capacitated Domination and Covering: A Parameterized Perspective
• On the complexity of edge traversing
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Matching, Euler tours and the Chinese postman
• Networks and vehicle routing for municipal waste collection
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth