Exact arborescences, matchings and cycles

DOI10.1016/0166-218X(87)90067-9zbMath0632.05047MaRDI QIDQ1095157

Francisco Barahona, William R. Pulleyblank

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

planar graphsdirected graphpolynomial algorithmsarborescenceexact cycleexact perfect matchingexact spanning treeplanar directed graphs

Mathematics Subject Classification ID

Graph theory (05C99) Directed graphs (digraphs), tournaments (05C20)

Related Items (25)

Knapsack problem with objective value gaps ⋮ Heuristic and exact algorithms for the spanning tree detection problem ⋮ Decision-making based on approximate and smoothed Pareto curves ⋮ Random parallel algorithms for finding exact branchings, perfect matchings, and cycles ⋮ Approximation of min-max and min-max regret versions of some combinatorial optimization problems ⋮ Optimizing over a slice of the bipartite matching polytope ⋮ Simple paths with exact and forbidden lengths ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem ⋮ New approaches to multi-objective optimization ⋮ General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems ⋮ A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. ⋮ The image of weighted combinatorial problems ⋮ Budgeted colored matching problems ⋮ A polynomial time equivalence between DNA sequencing and the exact perfect matching problem ⋮ Random pseudo-polynomial algorithms for some combinatorial programming problems ⋮ On the difficulty of finding walks of length k ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Cooperation in Multiorganization Matching ⋮ The complexity of bottleneck labeled graph problems ⋮ Semi-preemptive routing on trees ⋮ Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems ⋮ Approximation algorithms for multi-criteria traveling salesman problems ⋮ A polynomial solvable minimum risk spanning tree problem with interval data ⋮ Randomized algorithms over finite fields for the exact parity base problem.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix tree theorems
• Efficient algorithms for a family of matroid intersection problems
• The complexity of restricted spanning tree problems
• A good algorithm for smallest spanning trees with a degree constraint
• Packing rooted directed cuts in a weighted directed graph
• Optimum branchings
• Systems of distinct representatives and linear algebra

This page was built for publication: Exact arborescences, matchings and cycles