Skip to main content
SpringerLink
Log in

Forests, frames, and games: Algorithms for matroid sums and applications

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

This paper presents improved algorithms for matroid-partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned intok forests, and finding as many disjoint spanning trees as possible. The notion of a clump in a matroid sum is introduced, and efficient algorithms for clumps are presented. Applications of these algorithms are given to problems arising in the study of the structural rigidity of graphs, the Shannon switching game, and others.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. Aigner,Combinatorial Theory, Springer-Verlag, New York, 1979.

    MATH  Google Scholar 

  2. J. Bruno, Matroids, Graphs and Resistance Networks, Ph.D. Dissertation, Dept. Electrical Engineering, City College of New York, New York, 1967.

    Google Scholar 

  3. J. Bruno and L. Weinberg, A constructive graph-theoretic solution of the Shannon switching game,IEEE Trans. Circuit Theory,17(1), 1970, 74–81.

    MathSciNet  Google Scholar 

  4. J. Bruno and L. Weinberg, The principal minors of a matroid,Linear Algebra Appl.,4, 1971, 17–54.

    Article  MATH  MathSciNet  Google Scholar 

  5. N. Chiba and T. Nishizeki, Arboricity and subgraph listing algorithms,SIAM J. Comput.,14(1), 1985, 210–223.

    Article  MATH  MathSciNet  Google Scholar 

  6. E. A. Dinic, Algorithm for solution of a problem of maximum flow in a network with power estimation,Soviet Math. Dokl.,11(5), 1970, 1277–1280.

    Google Scholar 

  7. J. Edmonds, Minimum partition of a matroid into independent subsets,J. Res. Nat. Bur. Standards,69B, 1965, 67–72.

    MathSciNet  Google Scholar 

  8. J. Edmonds, Lehman's switching game and a theorem of Tutte and Nash-Williams,J. Res. Nat. Bur. Standards,69B, 1965, 73–77.

    MathSciNet  Google Scholar 

  9. S. Even and R. E. Tarjan, Network flow and testing graph connectivity,SIAM J. Comput.,4(4), 1975, 507–518.

    Article  MATH  MathSciNet  Google Scholar 

  10. G. N. Frederickson, Data structures for on-line updating of minimum spanning trees, with applications,SIAM J. Comput.,14(4), 1985, 781–798.

    Article  MATH  MathSciNet  Google Scholar 

  11. H. N. Gabow and M. Stallmann, Efficient algorithms for graphic matroid intersection and parity,Automata, Languages and Programming: 12th Colloquium, Lecture Notes in Computer Science, Vol. 194, W. Brauer, ed., Springer-Verlag, Berlin, 1985, pp. 210–220.

    Google Scholar 

  12. H. N. Gabow and R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union,J. Comput. System Sci.,30(2), 1985, 209–221.

    Article  MATH  MathSciNet  Google Scholar 

  13. H. N. Gabow and R. E. Tarjan, A linear-time algorithm for finding a minimum spanning pseudoforest,Inform. Process. Lett.,27(5), 1988, 259–263.

    Article  MATH  MathSciNet  Google Scholar 

  14. H. N. Gabow and R. E. Tarjan, Algorithms for two bottleneck optimization problems,J. Algorithms,9(3), 1988, 411–417.

    Article  MATH  MathSciNet  Google Scholar 

  15. H. N. Gabow and R. E. Tarjan, Almost-optimum speed-ups of algorithms for bipartite matching and related problems,Proc. 20th Annual ACM Symp. on Theory of Computing, 1988, pp. 514–527.

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

    Article  MATH  MathSciNet  Google Scholar 

  17. D. Gusfield, Connectivity and edge-disjoint spanning trees,Inform. Process. Lett.,16, 1983, 87–89.

    Article  MATH  MathSciNet  Google Scholar 

  18. J. Hopcroft and R. Karp, Ann 5/2 algorithm for maximum matchings in bipartite graphs,SIAM J. Comput.,2(4), 1973, 225–231.

    Article  MATH  MathSciNet  Google Scholar 

  19. H. Imai, Network-flow algorithms for lower-truncated transversal polymatroids,J. Oper. Res. Soc. Japan,26(3), 1983, 186–210.

    MATH  MathSciNet  Google Scholar 

  20. M. Iri and S. Fujishige, Use of matroid theory in operations research, circuits and systems theory,Internat. J. Systems Sci.,12(1), 1981, 27–54.

    Article  MATH  MathSciNet  Google Scholar 

  21. A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks,Inform. and Control,79, 1988. 43–59.

    MATH  MathSciNet  Google Scholar 

  22. G. Kishi and Y. Kajitani, Maximally distant trees and principal partition of a linear graph,IEEE Trans. Circuit Theory,16(3), 1969, 323–330.

    MathSciNet  Google Scholar 

  23. G. Laman, On graphs and rigidity of plane skeletal structures,J. Engrg. Math.,4(4), 1970, 331–340.

    Article  MATH  MathSciNet  Google Scholar 

  24. E. L. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rhinehart, and Winston, New York, 1976.

    MATH  Google Scholar 

  25. A. Lehman, A solution to the Shannon switching game,J. Soc. Indust. Appl. Math.,12, 1964, 687–725.

    Article  MATH  MathSciNet  Google Scholar 

  26. L. Lovász and Y. Yemini, On generic rigidity in the plane,SIAM J. Algebraic Discrete Methods,3, 1982, 91–98.

    Article  MATH  MathSciNet  Google Scholar 

  27. L. R. Matthews, Bicircular matroids,Quart. J. Math. Oxford,28(2), 1977, 213–228.

    Article  MATH  MathSciNet  Google Scholar 

  28. C. St. J. A. Nash-Williams, Edge-disjoint spanning trees of finite graphs,J. London Math. Soc.,36, 1961, 445–450.

    Article  MATH  MathSciNet  Google Scholar 

  29. T. Ohtsuki, Y. Ishizaki, and H. Watanabe, Topological degrees of freedom and mixed analysis of electrical networks,IEEE Trans. Circuit Theory,17(4), 1970, 491–499.

    Article  MathSciNet  Google Scholar 

  30. 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, 141–159.

    Article  MATH  MathSciNet  Google Scholar 

  31. A. Recski,Matroid Theory and Its Applications in Electric Network Theory and in Statics, Springer-Verlag, New York, 1989.

    Google Scholar 

  32. J. Roskind and R. E. Tarjan, A note on finding minimum-cost edge-disjoint spanning trees,Math. Oper. Res.,10(4), 1985, 701–708.

    MATH  MathSciNet  Google Scholar 

  33. B. Servatuis, Birigidity in the plane,SIAM J. Discrete Math.,2(4), 1989, 582–589.

    Article  MathSciNet  Google Scholar 

  34. D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees,J. Comput. System Sci.,26, 1983, 362–391.

    Article  MATH  MathSciNet  Google Scholar 

  35. R. E. Tarjan,Data Structures and Network Algorithms, SIAM Monograph, Philadelphia, PA, 1983.

  36. T.-S. Tay, Rigidity of multi-graphs. I. Linking rigid bodies inn-space,J. Combin. Theory Ser. B,36, 1984, 95–112.

    Article  MATH  MathSciNet  Google Scholar 

  37. W. T. Tutte, On the problem of decomposing a graph into connected factors,J. London Math. Soc.,36, 1961, 221–230.

    Article  MATH  MathSciNet  Google Scholar 

  38. D. J. A. Welsh,Matroid Theory, Academic Press, New York, 1976.

    MATH  Google Scholar 

  39. H. H. Westermann, Efficient Algorithms for Matroid Sums, Ph.D. Dissertation, Dept. Computer Science, University of Colorado at Boulder, Boulder, CO, 1987.

    Google Scholar 

  40. N. White and W. Whiteley, The algebraic geometry of motions of bar-and-body frameworks,SIAM J. Algebraic Discrete Methods,8(1), 1987, 1–32.

    Article  MATH  MathSciNet  Google Scholar 

  41. W. Whiteley, The union of matroids and the rigidity of frameworks,SIAM J. Discrete Math.,1(2), 1988, 237–255.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Colorado at Boulder, 80309, Boulder, CO, USA

    Harold N. Gabow

  2. Department 3228, IBM Laboratories, Schönaidner Strasse 220, 7030, Böblingen, Germany

    Herbert H. Westermann

Authors
  1. Harold N. Gabow
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Herbert H. Westermann
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Greg N. Frederickson.

This is a revised and expanded version of a paper appearing in theProceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988. This research was supported in part by National Science Foundation Grants MCS-8302648 and DCR-851191.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gabow, H.N., Westermann, H.H. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica 7, 465–497 (1992). https://doi.org/10.1007/BF01758774

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01758774

Key words

Search

Navigation