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

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 into k forests. The notion of a clamp in a matroid sum is introduced. Efficient algorithms for problems involving clumps are presented. Applications of these algorithms to problems arising in the study of structural rigidity of graphs, the Shannon switching game and others are given.

REFERENCES

• A: M. Aigner, ('ombinotorial Theory, Spriage,'-Vorlag, New York, 197,{).
• B: John Bruno, ",\lat. roitls graphs and r('si.,,tance networks", Ph.D. {lis.sertation, I)ept. Elee. Eng., City College of New York, New York. l:)67.
• BW70: J. Bruno and L. Weinberg, "A constructive graph-lheoretic solution of l llo ~haltnoll s~,,'itching ganle", IEEE Trans. Curcuit theory ( T-17, 1, 1970,pp. 74-81.
• BW71: J. Bruno and L. Weinberg, "Tile prilicipal lttinors ,ff a inatroi(l", Linear algebra and Its Apphcations,l. 1971. pp. t7- 5.1.
• CN: Norishige Chiba , Takao Nishizeki, Arboricity and subgraph listing algorithms, SIAM Journal on Computing, v.14 n.1, p.210-223, Feb. 1985 [doi>10.1137/0214017]
• D: E.A. Dinic, "Algorithm for solution of a problem of maximum flow in a network with power estimat ion", Nor. Math. Dokl. It, ,5, 1970. pp. t277-1280.
• Ed65a: J. Edmonds, "Miaimum partition of a matroid into ind,-- pendent subsets". J. Res. National Bureau of Standards 6911, 196,5, pp. 67-72.
• Ed65b: J. Edmonds, "Lehmau's switching same and a theorem of Tutte, and Nash-Williams". d. tte.~. National But'cart of Standarda 6911, 1~,)65, pp. 73-77.
• ET: S. Even and R.E. Tarjan, "Network flow and testing graph coEineclivity", SL4'M J. compul. 4, 4, 197fi, pp. 507-518.
• GS: Harold N. Gabow , Matthias Stallmann, Efficient Algorithms for Graphic Intersection and Parity (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.210-220, July 15-19, 1985
• GT83: Harold N. Gabow , Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.246-251, December 1983 [doi>10.1145/800061.808753]
• GT87a: Harold N. Gabow , Robert E. Tarjan, A linear-time algorithm for finding a minimum spanning pseudoforest, Information Processing Letters, v.27 n.5, p.259-263, April 28, 1988 [doi>10.1016/0020-0190(88)90089-0]
• GT87b: B. N Gabow and R. E. Tarjan. "Algorithms for two boothiieck Ol~ti,~}ization prol~h,lli..4", manuscript.
• GT88: Harold Gabow , Robert Tarjan, Almost-optimum speed-ups of algorithms for bipartite matching and related problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.514-527, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62263]
• Gu83: D. Gusfiehl. "Connectivity alld edge-disjoint spanning trees", Inf. Proc. ~elters, 16. 1983. pp. 87-89.
• Gu87: D. Gusfield, "Conlputing the strength of a {mtwork in O(|V|3|e|) time", Tech. Rept. CSE-87-2. Comp. Sci. Div. Univ. Calofrornai Davis. 1987.
• HK: J. Hoperoh and R. Karp, "An n 3/2 algorithm for maximum ~natchirtgsin t~ipartitegraphs", .qt.t3{ .I (:omp. 2.,1, 1973, pl~,. 225:231.
• I: H. Imar, "Network-fow algorithms for lower-truncatcd transversal polymatroids", J. Op. Res. Soc. of Japan. 26, 3, 19S3.
• IF: M. lri and S. Fujishige, "Use of matroid theory in operations research, circuits and systems theory", Int. J, Systems Sci., L2, 1,L981, pp 27-54.
• IR: A. ltai and M. Rodeh, "The multi-tree approach to reliability in distributed networks", Proc. 25~a Annual S~,mp. on Found, of Comp. Sci., 1984, pp. 137-147.
• KK: G. Kishi and Y. Kajitani, "Maximally distant trees and principal partition of a linear graph", IEEE Trans. Circuit Theorq. C'.T-16, 3, I969, pp. 323-330.
• L: I,el,nsa~l. A.. "A solution 1.o the..Shannol)switching ga~m'" I. Soc. lndust. Appl. Math. 12 (P.)6.t).
• La: E.L. Lawler, Combinatortal Optimization: ,Vetworks and Matrotds, Holt, Rhinehart and Winston, New York, 1976
• LY: L. Lovasz and Y. Yemini, "On generic rigidity in the plane", SIAM I. Alg Disc. meth., 3. 1982, pp. 91-98.
• Ma: L.R. Matthews, -Bicircular matroids", Quarterly J. Math. O.tford. '28, 2.1977.pp , 213-22,';,
• NW: C. St J. A. Nash Williams. "Edge-disjoint spanning trees of finite graphs". London math. sec. 36. 1961, pp. 115- 150.
• OIW: T. Ohtsuki, Y. Ishizaki and H. Watanabe, "Topological degrecs of freedom mixed analysis of electical nettworks", tEEE 'Trans. current theory, cf. 17, 1. 1970.pp,191-199.
• PQ: J.-C. Picar(I and hl, Qimyra~ltl~', "A network flow .solution to some nonlinear 0-1 programming problems, with applications to graph theory", Networks. 12. 1982. pp. 14t-159.
• RT: J. Roskind and R.E. Tarjan, :'A note on finding minimumcost edge-disjoint spanning trees", Math, Op. Res. I0. 4, 1985, pp. 701-708.
• ST: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• Tay: F-S. Tay, "Rigidity of nlulti-graphs. I. Linking rigid bodio,~ in n-space", .I, comb. Tb. B, 31;, 1984, pp..95-112.
• Tu: W. 'F. Tutte. "On th,, problem, of decomposing a graph into cm~n,'cted factors", J.London math. soc 36 (1961),pp. 221-230.
• Wel: D.J.A. WcLsh, Matroul theory, Acadamic press,london, New York, San Francisco. 1976.
• Wes: H. H. Westermann, Efficient algorithms for matroid sums, University of Colorado at Boulder, Boulder, CO, 1988
• Wh: W. Whiteley, "The ttnion of matroids and the rigidity of frameworks", Champlain Regional College, St. Lambert, Quebec. Canada. 1986. preprint.
• WW: Neil White , Walter Whiteley, The algebraic geometry of motions of bar-and-body frameworks, SIAM Journal on Algebraic and Discrete Methods, v.8 n.1, p.1-32, January 2, 1987 [doi>10.1137/0608001]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory