scientific article; zbMATH DE number 7692724
From MaRDI portal
Publication:6155599
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 863470 (Why is no real title available?)
- scientific article; zbMATH DE number 3285076 (Why is no real title available?)
- scientific article; zbMATH DE number 3373559 (Why is no real title available?)
- A note on finding optimum branchings
- A simple derivation of edmonds' algorithm for optimum branchings
- Algorithm Theory - SWAT 2004
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Arborescence optimization problems solvable by Edmonds' algorithm
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Combinatorial optimization. Theory and algorithms
- Depth-First Search and Linear Graph Algorithms
- Digraphs
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Finding optimum branchings
- Geometric approximation algorithms
- Handbook of Approximation Algorithms and Metaheuristics
- Historical note on optimum spanning arborescences
- Models and heuristics for a minimum arborescence problem
- Optimum branchings
- P-Complete Approximation Problems
- Packing rooted directed cuts in a weighted directed graph
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- The design of approximation algorithms
Cited in
(19)- Precedence-constrained arborescences
- Arborescence optimization problems solvable by Edmonds' algorithm
- The Gilbert arborescence problem
- The complexity of finding arborescences in hypergraphs
- Robustness of minimum cost arborescences
- Exact arborescences, matchings and cycles
- Robustness of minimum cost arborescences
- A randomly weighted minimum arborescence with a random cost constraint
- Arborescence problems in directed graphs: theorems and algorithms
- Blocking optimal structures
- An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
- scientific article; zbMATH DE number 1931135 (Why is no real title available?)
- On the complexity of some arborescences finding problems on a multishop radio network
- The root location problem for arc-disjoint arborescences
- Reconfiguring (non-spanning) arborescences
- Heuristic and exact algorithms for minimum-weight non-spanning arborescences
- Counting minimum weight arborescences
- A simple algorithm and min-max formula for the inverse arborescence problem
- Blocking optimal \(k\)-arborescences
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)
