The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
From MaRDI portal
Publication:2701383
DOI10.1007/s00453-022-01064-1OpenAlexW4311374588MaRDI QIDQ2701383
Shao-hua Li, Karolina Okrasa, Manuel Sorge, Thomas Bellitto, Marcin Pilipczuk
Publication date: 28 April 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2009.12892
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The structure of graphs not admitting a fixed immersion
- Chinese postman problem on edge-colored multigraphs
- Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
- Two-factors in orientated graphs with forbidden transitions
- On the parameterized complexity of multiple-interval graph problems
- The directed subgraph homeomorphism problem
- Alternating cycles in edge-partitioned graphs
- Hamiltonian circuits determining the order of chromosomes
- A note on alternating cycles in edge-coloured graphs
- Which problems have strongly exponential complexity?
- On minimum connecting transition sets in graphs
- An FPT 2-approximation for tree-cut decomposition
- Separating codes and traffic monitoring
- Properly edge-colored theta graphs in edge-colored complete graphs
- Finding paths in graphs avoiding forbidden transitions
- Graph minors. XIII: The disjoint paths problem
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Complexity of trails, paths and circuits in arc-colored digraphs
- A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs
- Two disjoint shortest paths problem with non-negative edge length
- The undirected two disjoint shortest paths problem
- The power of cut-based parameters for computing edge disjoint paths
- The directed 2-linkage problem with length constraints
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Paths and trails in edge-colored graphs
- Cycle extension in edge-colored complete graphs
- Parametrized complexity theory.
- Finding Paths in Grids with Forbidden Transitions
- On s-t paths and trails in edge-colored graphs
- Algorithmic Applications of Tree-Cut Width
- Properly Coloured Cycles and Paths: Results and Open Problems
- Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- Trees in Graphs with Conflict Edges or Forbidden Transitions
- Finding Detours is Fixed-Parameter Tractable
- Immersions in Highly Edge Connected Graphs
- Finding Hamiltonian Cycle in Graphs of Bounded Treewidth
- The Directed Disjoint Shortest Paths Problem
- Alternating Hamiltonian cycles in $2$-edge-colored multigraphs
- Shortest Paths Avoiding Forbidden Subpaths
- Parameterized Algorithms
- Digraphs
- On the complexity of \(k\)-SAT
- Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
This page was built for publication: The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
