An Exact Algorithm to Check the Existence of (Elementary) Paths and a Generalisation of the Cut Problem in Graphs with Forbidden Transitions
From MaRDI portal
Publication:2927651
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
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