On conflict-free spanning tree: algorithms and complexity

DOI10.1007/978-3-030-95018-7_8MaRDI QIDQ6102267zbMATH OpenOpenAlexFDO

Authors Bruno José S. Barros, Luiz S. Ochi, Rian G. S. Pinheiro, Uéverton S. Souza

Publication date 8 May 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-95018-7_8

zbMATH Keywords

approximationconflict-freeFPTspanning tree

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

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

Cites work

• A unifying model for locally constrained spanning tree problems
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Faster parameterized algorithm for cluster vertex deletion
• Heuristics and lower bounds for the bin packing problem with conflicts
• On the History of the Minimum Spanning Tree Problem
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Paths, trees and matchings under disjunctive constraints
• Planar 3-SAT with a clause/variable cycle
• The Knapsack Problem with Conflict Graphs
• The minimum spanning tree problem with conflict constraints and its variations

Cited in

(3)

• Parameterized complexity of conflict-free matchings and paths
• On conflict-free cuts: algorithms and complexity
• On conflict-free spanning tree: mapping tractable and hard instances through the lenses of graph classes

This page was built for publication: On conflict-free spanning tree: algorithms and complexity

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