Almost disjoint paths and separating by forbidden pairs

DOI10.1016/j.tcs.2023.114272arXiv2202.10090OpenAlexW4387967528MaRDI QIDQ6199396

Sven O. Krumke, Oliver Bachtler, Unnamed Author

Publication date: 23 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

complexitydynamic programminggraph algorithmsdirected acyclic graphsalmost disjoint pathspath avoiding forbidden pairs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the path avoiding forbidden pairs polytope
• The disjoint paths problem in quadratic time
• On paths avoding forbidden pairs of vertices in a graph
• On finding dissimilar Pareto-optimal paths
• On the complexity of paths avoiding forbidden pairs
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• On finding dissimilar paths
• Parameterized complexity in the polynomial hierarchy. Extending parameterized complexity theory to higher levels of the hierarchy
• Complexity of the path avoiding forbidden pairs problem revisited
• Alternative Route Graphs in Road Networks
• Disjoint paths in a network
• On the Complexity of Timetable and Multicommodity Flow Problems
• Computational Complexity

This page was built for publication: Almost disjoint paths and separating by forbidden pairs