Article

Free access

Algorithms for graphic polymatroids and parametric s-Sets

Author:

Harold N. GabowAuthors Info & Claims

SODA '95: Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms

Pages 88 - 97

Published: 22 January 1995 Publication History

PDF eReader

References

[1]

R.K. Ahuja, J. B. Orlin, C. Stein and R. E. Tarjan, Improved algorithms for bipartite network flow, SIAM J. Comput., 23, 5 (1994), pp. 906-933.

Digital Library

Google Scholar

[2]

F. Barahona, Separating from the dominant of the spanning tree polytope, Op. Res. Letters, 12 (1992), pp. 201-203.

Google Scholar

[3]

S. Baum and L. E. Trotter, Jr., Integer rounding for polymatroid and branching optimization problems, SIAM J. Alg. Disc. Meth., 2, 4 (1981), pp. 416-425.

Google Scholar

[4]

E. Cheng and W. H. Cunningham, A faster algorithm for computing the strength of a network, Inf. Proc. Letters, 49 (1994), pp. 209-212.

Digital Library

Google Scholar

[5]

W.H. Cunningham, Optimal attack and reinforcement of a network, J. ACM, 32, 3 (1985), pp. 549-561.

Digital Library

Google Scholar

[6]

---, Minimum cuts, modular functions and matroid polyhedra, Networks, 15 (1985), pp. 205-215.

Google Scholar

[7]

W. Dinkelbach, On nonlinear fractional programming, Management Sci., 13 (1967), pp. 492-498.

Google Scholar

[8]

J. Edmonds, Lehman's switching game and a theorem of Tutte and Nash-Williams, J. Res. National Bureau of Standards, 69B (1965), pp. 73-77.

Google Scholar

[9]

---, Submodular functions, matroids, and certain polyhedra in Calgary International Conf. on Combinatorial Structures and their Applications, Gordon and Breach, New York, 1969, pp. 69-87.

Google Scholar

[10]

H.N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proc. 23rd Annual ACM Syrup. on Theory of Comp. {1991), pp. 112-122; J. CSS, to appear.

Digital Library

Google Scholar

[11]

---, E~cient splitting off algorithms for graphs, Proc. 26th Annual ACM Symp. on Theory of Comp. (1994), pp. 696-705.

Digital Library

Google Scholar

[12]

H. N. Gabow and K. S. Mann, Packing algorithms for arborescences (and spanning trees) in capacitated graphs, preprint.

Google Scholar

[13]

H.N. Gabow and H. H. Westermann, Forests, frames and games: Algorithms for matroid sums and applications, Algorithmica, 7 (1992), pp. 465-497.

Google Scholar

[14]

G. Gallo, M. D. Grigoriadis and R. E. Tarjan, A fast parametric maximum flow algorithm and applications, SIAM J. Comput., 18, i (1989), pp. 30-55.

Digital Library

Google Scholar

[15]

F.R. Giles, Submodular functions, graphs and integer polyhedra, P h. D. Dissertation, Dept. of Combinatorics and Optimization, Univ. of Waterloo, Waterloo, Ontario, 1975.

Google Scholar

[16]

A.V. Goldberg and R. lg. Tarjan, A new approach to the maximum flow-problem, J. ACM, 35, 4 (1988), pp. 921-940.

Digital Library

Google Scholar

[17]

D. Gusfield, Connectivity and edge-disjoint 8panning trees, Inf. Proc. Letters, 16, 2 (1983), pp. 87-89.

Google Scholar

[18]

----, Computing the strength of a graph, SIAM J. Comput., 20, 4 (1991), pp. 639-654.

Digital Library

Google Scholar

[19]

J. Hao and j. B. Orlin, A faster algorithm for finding the minimum cut in a graph, Proc. 3rd Annual ACM- SIAM Symp. on Disc. Algorithms (1992), pp. 165-174.

Digital Library

Google Scholar

[20]

F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969.

Google Scholar

[21]

M.W. Padberg and L. A. Wolsey, Trees and cuts, Ann. Discrete Math., 17 (1983), pp. 511-517.

Google Scholar

[22]

---, Fractional covers .for forests and matchings, Math. Programming, 29 (1984), pp. 1-14.

Google Scholar

[23]

S. Phillips and J. Westbrook, Online load balancing and network flow, Proc. 25th Annual ACM Symp. on Theory of Comp. (1993), pp. 402-411.

Digital Library

Google Scholar

[24]

J.-C. Picard and M. Queyranne, A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory, Networks, 12 (1982), pp. 141-159.

Google Scholar

[25]

---, Selected applications of minimum cut8 in networks, iNFOR, 20 (1982), pp. 394-422.

Google Scholar

[26]

S. Schaible, Fractional programming II. On Dinkelbach's algorithm, Management Sci., 22 (1976), pp. 868- 873.

Google Scholar

[27]

Matroid Theory, Academic Press, New York, 1976.

Google Scholar

Cited By

View all

Zhang COu Y(2008)Clustering, community partition and disjoint spanning treesACM Transactions on Algorithms10.1145/1367064.13670754:3(1-26)Online publication date: 4-Jul-2008
https://dl.acm.org/doi/10.1145/1367064.1367075
Frederickson GSolis-Oba RSaks M(1997)Efficient algorithms for robustness in matroid optimizationProceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms10.5555/314161.314411(659-668)Online publication date: 5-Jan-1997
https://dl.acm.org/doi/10.5555/314161.314411

Index Terms

Algorithms for graphic polymatroids and parametric s-Sets
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Obstructions to a binary matroid being graphic

Bixby and Cunningham showed that a 3-connected binary matroid M is graphic if and only if every element belongs to at most two non-separating cocircuits. Likewise, Lemos showed that such a matroid M is graphic if and only if it has exactly r(M)+1 non-...
On graphic elementary lifts of graphic matroids
Abstract
An elementary lift of a binary matroid M that arises from a binary coextension of M can easily be obtained by applying the splitting operation on M. This operation on a graphic matroid may not produce a graphic matroid. We give a ...
Describing quasi-graphic matroids
Abstract
The class of quasi-graphic matroids recently introduced by Geelen, Gerards, and Whittle generalises each of the classes of frame matroids and lifted-graphic matroids introduced earlier by Zaslavsky. For each biased graph ( G , B ) ...

Comments

Information & Contributors

Information

Published In

SODA '95: Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms

January 1995

654 pages

ISBN:0898713498

Chairman:
Kenneth Clarkson

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 1995

Check for updates

Qualifiers

Article

Conference

SODA95

Sponsor:

SIGACT
SIAM

SODA95: Conference on Discrete Algorithms

January 22 - 24, 1995

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
345
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)12

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang COu Y(2008)Clustering, community partition and disjoint spanning treesACM Transactions on Algorithms10.1145/1367064.13670754:3(1-26)Online publication date: 4-Jul-2008
https://dl.acm.org/doi/10.1145/1367064.1367075
Frederickson GSolis-Oba RSaks M(1997)Efficient algorithms for robustness in matroid optimizationProceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms10.5555/314161.314411(659-668)Online publication date: 5-Jan-1997
https://dl.acm.org/doi/10.5555/314161.314411

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Obstructions to a binary matroid being graphic

On graphic elementary lifts of graphic matroids

Describing quasi-graphic matroids