Complexity of the path avoiding forbidden pairs problem revisited

DOI10.1016/j.dam.2012.12.022zbMath1287.05071arXiv1111.3996OpenAlexW2164225775MaRDI QIDQ2446333

Jakub Kováč

Publication date: 16 April 2014

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

Full work available at URL: https://arxiv.org/abs/1111.3996

zbMATH Keywords

dynamic programmingpathNP-hardforbidden pair

Mathematics Subject Classification ID

Dynamic programming (90C39) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

On the path avoiding forbidden pairs polytope ⋮ Analyzing the reachability problem in choice networks ⋮ Reachability in choice networks ⋮ Precedence-constrained arborescences ⋮ Shortest paths with exclusive-disjunction arc pairs conflicts ⋮ Almost disjoint paths and separating by forbidden pairs ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ Domination problems with no conflicts

Uses Software

• CUDA

Cites Work

• Unnamed Item
• Unnamed Item
• On paths avoding forbidden pairs of vertices in a graph
• Matrix multiplication via arithmetic progressions
• On the complexity of paths avoiding forbidden pairs
• Finding paths and deleting edges in directed acyclic graphs
• General context-free recognition in less than cubic time
• Impossible pair constrained test path generation in a program
• Kernel Bounds for Path and Cycle Problems
• The Checkpoint Problem