A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

DOI10.1007/BF01589417zbMath0665.90076MaRDI QIDQ1116893

Carl Brezovec, Fred Glover, Cornuéjols, Gérard

Publication date: 1988

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

traveling salesmanmatroidminimum weight spanning treeminimum weight baseupper and lower bound restrictionsweighted bipartite matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

The structural complexity landscape of finding balance-fair shortest paths, Two algorithms for weighted matroid intersection, An Approximation Algorithm for the Three Depots Hamiltonian Path Problem, Biobjective optimization problems on matroids with binary costs, The minimum spanning tree problem with conflict constraints and its variations, Making Bipartite Graphs DM-Irreducible, A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees, Color constrained combinatorial optimization problems, On the generality of the greedy algorithm for solving matroid base problems, The \(k\)-path tree matroid and its applications to survivable network design, Crashing a maximum-weight complementary basis, Approximation algorithms for multiple terminal, Hamiltonian path problems, How to allocate review tasks for robust ranking, \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• Constrained spanning trees and the traveling salesman problem
• Matroid Intersection
• Efficient algorithms for a family of matroid intersection problems
• Two algorithms for weighted matroid intersection
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II