On the complexity of paths avoiding forbidden pairs

DOI10.1016/j.dam.2009.03.018zbMath1209.05245OpenAlexW2114795697MaRDI QIDQ967328

Petr Kolman, Ondřej Pangrác

Publication date: 28 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2009.03.018

zbMATH Keywords

algorithmpathforbidden pairs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

On the path avoiding forbidden pairs polytope ⋮ Analyzing the reachability problem in choice networks ⋮ Kernel bounds for path and cycle problems ⋮ Reachability in choice networks ⋮ Shortest paths with exclusive-disjunction arc pairs conflicts ⋮ Almost disjoint paths and separating by forbidden pairs ⋮ Parameterized complexity of Eulerian deletion problems ⋮ Complexity of the path avoiding forbidden pairs problem revisited ⋮ On finding the longest antisymmetric path in directed acyclic graphs ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ A network model for routing-fault-free wavelength selection in WRONoCs design ⋮ Domination problems with no conflicts ⋮ Trees in Graphs with Conflict Edges or Forbidden Transitions ⋮ The checkpoint problem ⋮ Parameterized Complexity of Eulerian Deletion Problems

Cites Work

• On paths avoding forbidden pairs of vertices in a graph
• Finding paths and deleting edges in directed acyclic graphs
• Impossible pair constrained test path generation in a program
• Mathematical Foundations of Computer Science 2003

This page was built for publication: On the complexity of paths avoiding forbidden pairs