The mixed Chinese postman problem parameterized by pathwidth and treedepth
From MaRDI portal
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45) Signed and weighted graphs (05C22)
Recommendations
- Structural parameterizations of the mixed Chinese postman problem
- Parameterized Complexity of the k-Arc Chinese Postman Problem
- Parameterized complexity of the k-arc Chinese postman problem
- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- Parameterized complexity of \(k\)-Chinese postman problem
Cites work
- scientific article; zbMATH DE number 3724496 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Arc Routing Problems, Part I: The Chinese Postman Problem
- Capacitated Domination and Covering: A Parameterized Perspective
- Fundamentals of parameterized complexity
- Matching, Euler tours and the Chinese postman
- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- Networks and vehicle routing for municipal waste collection
- On the complexity of edge traversing
- On the complexity of some colorful problems parameterized by treewidth
- Parameterized Complexity of the k-Arc Chinese Postman Problem
- Parameterized algorithms
- Parameterized complexity of generalized domination problems
- Parametrized complexity theory.
- Structural parameterizations of the mixed Chinese postman problem
- The complexity of arc routing problems
- Treewidth. Computations and approximations
Cited in
(23)- The parameterized complexity of the minimum shared edges problem
- Fine-grained parameterized complexity analysis of graph coloring problems
- Grundy Distinguishes Treewidth from Pathwidth
- Structural parameterizations of the biclique-free vertex deletion problem
- Parameterized Complexity of the k-Arc Chinese Postman Problem
- Slim tree-cut width
- Parameterized algorithms for book embedding problems
- Parameterized algorithms for queue layouts
- Fine-grained meta-theorems for vertex integrity
- On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
- Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
- On fixed-order book thickness parameterized by the pathwidth of the vertex ordering
- Parameterized algorithms for book embedding problems
- Parameterized complexity of the k-arc Chinese postman problem
- Grundy distinguishes treewidth from pathwidth
- A heuristic approach to the treedepth decomposition problem for large graphs
- Length-bounded cuts: proper interval graphs and structural parameters
- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- Slim tree-cut width
- Structural parameterizations of the mixed Chinese postman problem
- Parameterized Algorithms for Queue Layouts
This page was built for publication: The mixed Chinese postman problem parameterized by pathwidth and treedepth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835842)
