The mixed Chinese postman problem parameterized by pathwidth and treedepth
From MaRDI portal
Signed and weighted graphs (05C22) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)
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
- 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
- scientific article; zbMATH DE number 3724496 (Why is no real title available?)
- 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 algorithms
- Parameterized complexity of generalized domination problems
- Parameterized Complexity of the k-Arc Chinese Postman Problem
- Parametrized complexity theory.
- Structural parameterizations of the mixed Chinese postman problem
- The complexity of arc routing problems
- Treewidth. Computations and approximations
Cited in
(25)- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- 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
- Fine-grained parameterized complexity analysis of graph coloring problems
- Length-bounded cuts: proper interval graphs and structural parameters
- Parameterized algorithms for book embedding problems
- The parameterized complexity of the minimum shared edges problem
- 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
- Parameterized Complexity of the k-Arc Chinese Postman Problem
- Parameterized complexity of the k-arc Chinese postman problem
- Structural parameterizations of the mixed Chinese postman problem
- Parameterized Algorithms for Queue Layouts
- Parameterized algorithms for queue layouts
- Grundy Distinguishes Treewidth from Pathwidth
- Parameterized algorithms for book embedding problems
- 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
- Slim tree-cut width
- Slim tree-cut width
- Structural parameterizations of the biclique-free vertex deletion problem
- Fine-grained meta-theorems for vertex integrity
- Bounding width on graph classes of constant diameter
- Balancing the spread of two opinions in sparse social networks
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)
