Finding paths in graphs avoiding forbidden transitions

DOI10.1016/S0166-218X(02)00251-2zbMath1010.68099OpenAlexW2101752896MaRDI QIDQ1861577

Stefan Szeider

Publication date: 9 March 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00251-2

zbMATH Keywords

NP-completenesslinear time algorithmtransition systemstransitiontransition graphedge-colored graphforbidden pairscompatible path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (22)

Paths and trails in edge-colored graphs ⋮ Analyzing the reachability problem in choice networks ⋮ Shortest paths avoiding forbidden subpaths ⋮ Codon optimization by 0-1 linear programming ⋮ Some Hamiltonian Properties of One-Conflict Graphs ⋮ Fractional cycle decompositions in hypergraphs ⋮ Unnamed Item ⋮ Reachability in choice networks ⋮ Separating codes and traffic monitoring ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ Odd properly colored cycles in edge-colored graphs ⋮ The complexity landscape of decompositional parameters for ILP ⋮ Trees in Graphs with Conflict Edges or Forbidden Transitions ⋮ Two-factors in orientated graphs with forbidden transitions ⋮ Paths and Trails in Edge-Colored Graphs ⋮ Finding Paths in Grids with Forbidden Transitions ⋮ Properly Coloured Cycles and Paths: Results and Open Problems ⋮ On s-t paths and trails in edge-colored graphs ⋮ Paths and trails in edge-colored weighted graphs ⋮ On edge-colored graphs covered by properly colored cycles ⋮ Finding disjoint paths in networks with star shared risk link groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compatible path-cycle-decompositions of plane graphs
• Eulerian graphs and related topics. Part 1, Volume 1
• Compatible 2-factors
• Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
• On circuit decomposition of planar Eulerian graphs
• A Short Proof of the Factor Theorem for Finite Graphs

This page was built for publication: Finding paths in graphs avoiding forbidden transitions