Trees in graphs with conflict edges or forbidden transitions

DOI10.1007/978-3-642-38236-9_31MaRDI QIDQ4922140zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Paths, trees and matchings under disjunctive constraints
• On minimum connecting transition sets in graphs
• The minimum spanning tree problem with conflict constraints and its variations
• A branch and cut algorithm for minimum spanning trees under conflict constraints

Cites work

• An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions
• Finding paths in graphs avoiding forbidden transitions
• Graph theory
• Graphic sequences of trees and a problem of Frobenius
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• On the complexity of paths avoiding forbidden pairs
• Paths, trees and matchings under disjunctive constraints
• The Knapsack Problem with Conflict Graphs
• Two-factors in orientated graphs with forbidden transitions

Cited in

(11)

• On minimum connecting transition sets in graphs
• 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
• Optimal Steiner trees under node and edge privacy conflicts
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• Some Hamiltonian properties of one-conflict graphs
• Expected conflicts in pairs of rooted binary trees
• scientific article; zbMATH DE number 7765417 (Why is no real title available?)
• A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
• Paths, trees and matchings under disjunctive constraints

This page was built for publication: Trees in graphs with conflict edges or forbidden transitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4922140)