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
branchinginapproximabilitymaximum degreeNP-hardnessarborescencenew proofEdmonds' algorithmspanning arborescence
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)