Rural postman parameterized by the number of components of required edges
From MaRDI portal
Publication:314816
DOI10.1016/J.JCSS.2016.06.001zbMATH Open1350.68144OpenAlexW2494101910MaRDI QIDQ314816FDOQ314816
Authors: G. Gutin, Magnus Wahlström, A. Yeo 
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
Recommendations
- scientific article; zbMATH DE number 27244
- A polyhedral approach to the rural postman problem
- An algorithm for the Rural Postman problem on a directed graph
- scientific article; zbMATH DE number 6741962
- The rural postman problem on directed, mixed, and windy graphs
- A note on the undirected rural postman problem polytope
- Algorithms for the rural postman problem
- Reoptimizing the rural postman problem
- The Rural Postman Problem on mixed graphs with turn penalties
- A branch-and-cut algorithm for the undirected rural postman problem
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Combinatorial optimization (90C27)
Cites Work
- Powers of tensors and fast matrix multiplication
- Fundamentals of parameterized complexity
- Matching theory
- Title not available (Why is that?)
- Parametrized complexity theory.
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Multiplying matrices faster than coppersmith-winograd
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Digraphs
- Title not available (Why is that?)
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- Title not available (Why is that?)
- Set partitioning via inclusion-exclusion
- Matching is as easy as matrix inversion
- On the complexity of edge traversing
- On general routing problems
- Approximation Algorithms for Some Postman Problems
- Title not available (Why is that?)
- Arc Routing Problems, Part II: The Rural Postman Problem
- On Eulerian extensions and their application to no-wait flowshop scheduling
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- Abusing the Tutte matrix: an algebraic instance compression for the \(K\)-set-cycle problem
- 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
- The complexity of arc routing problems
- Title not available (Why is that?)
Cited In (15)
- An algorithm for the Rural Postman problem on a directed graph
- Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
- Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- Efficient algorithms for Eulerian extension and rural Postman
- Basic Terminology, Notation and Results
- An updated annotated bibliography on arc routing problems
- On approximate data reduction for the Rural Postman Problem: Theory and experiments
- The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable
- Parameterized complexity of list coloring and max coloring
- A new view on rural postman based on Eulerian extension and matching
- Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
- An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
- On the complexity landscape of connected \(f\)-factor problems
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
This page was built for publication: Rural postman parameterized by the number of components of required edges
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q314816)
