Rural postman parameterized by the number of components of required edges
From MaRDI portal
Publication:314816
DOI10.1016/j.jcss.2016.06.001zbMath1350.68144OpenAlexW2494101910MaRDI QIDQ314816
Anders Yeo, Gregory Gutin, Magnus Wahlström
Publication date: 16 September 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2016.06.001
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Randomized algorithms (68W20)
Related Items (11)
Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks ⋮ An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable ⋮ On the complexity landscape of connected \(f\)-factor problems ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems ⋮ Basic Terminology, Notation and Results ⋮ Parameterized complexity of list coloring and max coloring
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Matching theory
- Matching is as easy as matrix inversion
- On Eulerian extensions and their application to no-wait flowshop scheduling
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- Parametrized complexity theory.
- Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
- Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
- Efficient Algorithms for Eulerian Extension
- From Few Components to an Eulerian Graph by Adding Arcs
- A New View on Rural Postman Based on Eulerian Extension and Matching
- Powers of tensors and fast matrix multiplication
- Set Partitioning via Inclusion-Exclusion
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- On the complexity of edge traversing
- On general routing problems
- Approximation Algorithms for Some Postman Problems
- Arc Routing Problems, Part II: The Rural Postman Problem
- Multiplying matrices faster than coppersmith-winograd
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Digraphs
This page was built for publication: Rural postman parameterized by the number of components of required edges
