An Exact Algorithm to Check the Existence of (Elementary) Paths and a Generalisation of the Cut Problem in Graphs with Forbidden Transitions

DOI10.1007/978-3-642-35843-2_23zbMath1303.05194OpenAlexW130304896MaRDI QIDQ2927651

Christian Laforest, Mamadou Moustapha Kanté, Benjamin Momège

Publication date: 4 November 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-35843-2_23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Some Hamiltonian Properties of One-Conflict Graphs, Introduction to routing problems with mandatory transitions, Domination problems with no conflicts, Trees in Graphs with Conflict Edges or Forbidden Transitions, On the complexity of independent dominating set with obligations in graphs