Finding paths in graphs avoiding forbidden transitions

DOI10.1016/S0166-218X(02)00251-2MaRDI QIDQ1861577zbMATH OpenOpenAlexFDO

Authors 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, https://durham-repository.worktribe.com/output/1565358

zbMATH Keywords

compatible pathedge-colored graphforbidden pairslinear time algorithmNP-completenesstransitiontransition graphtransition systems

Mathematics Subject Classification ID

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

Recommendations

• An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions
• Simple Paths and Cycles Avoiding Forbidden Paths
• Finding paths in grids with forbidden transitions
• On minimum connecting transition sets in graphs
• Two-factors in orientated graphs with forbidden transitions

Cites work

• A Short Proof of the Factor Theorem for Finite Graphs
• Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
• Compatible 2-factors
• Compatible path-cycle-decompositions of plane graphs
• Eulerian graphs and related topics. Part 1, Volume 1
• Graph theory.
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2192138 (Why is no real title available?)
• On circuit decomposition of planar Eulerian graphs

Cited in

(35)

• On minimum connecting transition sets in graphs
• Separating codes and traffic monitoring
• The complexity landscape of decompositional parameters for ILP
• Analyzing the reachability problem in choice networks
• Codon optimization by 0-1 linear programming
• Avoidable paths in graphs
• Paths and trails in edge-colored weighted graphs
• Finding disjoint paths in networks with star shared risk link groups
• Paths and trails in edge-colored graphs
• On edge-colored graphs covered by properly colored cycles
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• Finding paths in grids with forbidden transitions
• On \(s\)--\(t\) paths and trails in edge-colored graphs
• An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions
• Some Hamiltonian properties of one-conflict graphs
• Finding a contra-risk path between two nodes in undirected graphs
• Properly coloured cycles and paths: Results and open problems
• Trees in graphs with conflict edges or forbidden transitions
• scientific article; zbMATH DE number 7359421 (Why is no real title available?)
• Odd properly colored cycles in edge-colored graphs
• Simple Paths and Cycles Avoiding Forbidden Paths
• Shortest paths avoiding forbidden subpaths
• Shortest Paths Avoiding Forbidden Subpaths
• Paths and Trails in Edge-Colored Graphs
• Fractional cycle decompositions in hypergraphs
• scientific article; zbMATH DE number 7765417 (Why is no real title available?)
• Reachability in choice networks
• Trails in arc-colored digraphs avoiding forbidden transitions
• On the routing problems in graphs with ordered forbidden transitions
• The fine-grained complexity of approximately counting proper connected colorings (extended abstract)
• On paths avoding forbidden pairs of vertices in a graph
• An efficient branch-and-bound algorithm for the one-to-many shortest path problem with additional disjunctive conflict constraints
• (k,H)-kernels in nearly tournaments
• Pathfinding in self-deleting graphs
• Two-factors in orientated graphs with forbidden transitions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1861577)