Structural Parameterizations of the Mixed Chinese Postman Problem

DOI10.1007/978-3-662-48350-3_56zbMath1467.68074arXiv1410.5191OpenAlexW1901935697MaRDI QIDQ3452829

No author found.

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.5191

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (8)

Safe sets in graphs: graph classes and structural parameters ⋮ Safe Sets in Graphs: Graph Classes and Structural Parameters ⋮ The complexity landscape of decompositional parameters for ILP ⋮ Chinese postman problem on edge-colored multigraphs ⋮ Completing Partial Schedules for Open Shop with Unit Processing Times and Routing ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth

Cites Work

• Fundamentals of parameterized complexity
• Parameterized complexity of generalized domination problems
• On the complexity of some colorful problems parameterized by treewidth
• On the parameterized complexity of multiple-interval graph problems
• Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
• Parameterized Complexity of the k-Arc 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
• Unnamed Item
• Unnamed Item

This page was built for publication: Structural Parameterizations of the Mixed Chinese Postman Problem