Trees in Graphs with Conflict Edges or Forbidden Transitions

DOI10.1007/978-3-642-38236-9_31zbMath1382.68172OpenAlexW56005042MaRDI QIDQ4922140

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

Publication date: 28 May 2013

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-38236-9_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (8)

Optimal Steiner trees under node and edge privacy conflicts ⋮ Some Hamiltonian Properties of One-Conflict Graphs ⋮ A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ Domination problems with no conflicts ⋮ A unifying model for locally constrained spanning tree problems ⋮ On the complexity of independent dominating set with obligations in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Paths, trees and matchings under disjunctive constraints
• On the complexity of paths avoiding forbidden pairs
• Two-factors in orientated graphs with forbidden transitions
• Finding paths in graphs avoiding forbidden transitions
• An Exact Algorithm to Check the Existence of (Elementary) Paths and a Generalisation of the Cut Problem in Graphs with Forbidden Transitions
• The Knapsack Problem with Conflict Graphs
• Graphic sequences of trees and a problem of Frobenius

This page was built for publication: Trees in Graphs with Conflict Edges or Forbidden Transitions