Blocking optimal arborescences

DOI10.1007/s10107-016-1025-3zbMath1396.90071arXiv1506.05677OpenAlexW2887178071MaRDI QIDQ507342

Attila Bernáth, Gyula Pap, Gyula Pap

Publication date: 3 February 2017

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.05677

zbMATH Keywords

coveringpolynomial algorithmarborescences

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Global and fixed-terminal cuts in digraphs ⋮ A tight \(\sqrt{2} \)-approximation for linear 3-cut ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Blocking unions of arborescences ⋮ Blocking optimal structures

Cites Work

• Unnamed Item
• Unnamed Item
• Matching interdiction
• Reliable assignments of processors to tasks and factoring on matroids
• Blockers and transversals
• Finding the k most vital edges in the minimum spanning tree problem
• Computing girth and cogirth in perturbed graphic matroids
• An algorithm for source location in directed graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial Optimization
• Robustness of Minimum Cost Arborescences
• A weighted matroid intersection algorithm
• The intractability of computing the minimum distance of a code
• Packing rooted directed cuts in a weighted directed graph
• Packing Interdiction and Partial Covering Problems
• Increasing the Weight of Minimum Spanning Trees

This page was built for publication: Blocking optimal arborescences