scientific article; zbMATH DE number 7692724

zbMATH Open1519.05096MaRDI QIDQ6155599FDOQ6155599

Authors: Ján Plesník 

Publication date: 5 June 2023

Full work available at URL: http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1867

Title of this publication is not available (Why is that?)

Recommendations

• Blocking optimal arborescences
• Arborescence optimization problems solvable by Edmonds' algorithm
• Blocking optimal \(k\)-arborescences
• Blocking unions of arborescences
• Arborescence problems in directed graphs: theorems and algorithms

zbMATH Keywords

branchinginapproximabilitymaximum degreeNP-hardnessarborescencenew proofEdmonds' algorithmspanning arborescence

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07)

Cites Work

• The design of approximation algorithms
• Title not available (Why is that?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Depth-First Search and Linear Graph Algorithms
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Finding optimum branchings
• Digraphs
• Optimum branchings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• P-Complete Approximation Problems
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Handbook of Approximation Algorithms and Metaheuristics
• Geometric approximation algorithms
• Models and heuristics for a minimum arborescence problem
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Title not available (Why is that?)
• A note on finding optimum branchings
• Packing rooted directed cuts in a weighted directed graph
• A simple derivation of edmonds' algorithm for optimum branchings
• Combinatorial optimization. Theory and algorithms
• Algorithm Theory - SWAT 2004
• Arborescence optimization problems solvable by Edmonds' algorithm
• Historical note on optimum spanning arborescences

Cited In (19)

• The Gilbert arborescence problem
• Arborescence optimization problems solvable by Edmonds' algorithm
• Robustness of minimum cost arborescences
• Exact arborescences, matchings and cycles
• A simple algorithm and min-max formula for the inverse arborescence problem
• On the complexity of some arborescences finding problems on a multishop radio network
• Blocking optimal \(k\)-arborescences
• Robustness of minimum cost arborescences
• Arborescence problems in directed graphs: theorems and algorithms
• Counting minimum weight arborescences
• A randomly weighted minimum arborescence with a random cost constraint
• The root location problem for arc-disjoint arborescences
• Blocking optimal structures
• Reconfiguring (non-spanning) arborescences
• Title not available (Why is that?)
• Heuristic and exact algorithms for minimum-weight non-spanning arborescences
• The complexity of finding arborescences in hypergraphs
• Blocking optimal arborescences
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs

This page was built for publication:

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