A Weighted k_{t, t}-Free t-Factor Algorithm for Bipartite Graphs

References

• Cornuéjols G., Pulleyblank W. R. A matching problem with side conditions. Discrete Math. (1980) 29:135–159Crossref, Google Scholar
• Cunningham W. H. Matching, matroids, and extensions. Math. Program. (2002) 91:515–542Crossref, Google Scholar
• Cunningham W. H., Wang Y. Restricted 2-factor polytopes. Math. Program. (2000) 87:87–111Google Scholar
• Edmonds J., Karp R. M. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (1972) 19:248–264Crossref, Google Scholar
• Fleiner T. Uncrossing a family of set-pairs. Combinatorica (2001) 21:145–150Crossref, Google Scholar
• Frank A. Restricted t-matchings in bipartite graphs. Discrete Appl. Math. (2003) 131:337–346Crossref, Google Scholar
• Frank A., Jordán T. Minimal edge-coverings of pairs of sets. J. Combin. Theory Ser. B (1995) 65:73–110Crossref, Google Scholar
• Frank A., Tardos É. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica (1987) 7:49–65Crossref, Google Scholar
• Fredman M. L., Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM (1987) 34:596–615Crossref, Google Scholar
• Geelen J. F. The C6-free 2-factor problem in bipartite graphs is NP-complete. (1999) . UnpublishedGoogle Scholar
• Hartvigsen D. Extensions of matching theory. (1984) . Ph.D. thesis, Carnegie Mellon University, PittsburghGoogle Scholar
• Hartvigsen D., Cornuéjols G., Burkard R. E., Woeginger G. J. The square-free 2-factor problem in bipartite graphs. Integer Programming and Combinatorial Optimization (1999) (Springer-Verlag, Berlin) 234–241LNCS 1610Crossref, Google Scholar
• Hartvigsen D. Finding maximum square-free 2-matchings in bipartite graphs. J. Combin. Theory Ser. B (2006) 96:693–705Crossref, Google Scholar
• Hell P., Kirkpatrick D., Kratochvíl J., Kříž I. On restricted two-factors. SIAM J. Discrete Math. (1988) 1:472–484Crossref, Google Scholar
• Király Z. C4-free 2-matchings in bipartite graphs. (1999) . Technical Report TR-2001-13, Egerváry Research Group, BudapestGoogle Scholar
• Makai M. On maximum cost Kt, t-free t-matchings of bipartite graphs. SIAM J. Discrete Math. (2007) 21:349–360Crossref, Google Scholar
• Pap G. Alternating paths revisited II: Restricted b-matchings in bipartite graphs. (2005) . Technical Report TR-2005-13, Egerváry Research Group, BudapestGoogle Scholar
• Pap G. A constructive approach to matching and its generalizations. (2006) . Ph.D. thesis, Eötvös Loránd University, BudapestGoogle Scholar
• Pap G. Combinatorial algorithms for matchings, even factors and square-free 2-factors. Math. Program. (2007) 110:57–69Crossref, Google Scholar
• Russell M. Restricted two-factors. (2001) . Master's thesis, University of Waterloo, Ontario, CanadaGoogle Scholar
• Tomizawa N. On some techniques useful for solution of transportation network problems. Networks (1971) 1:173–194Crossref, Google Scholar
• Végh L. A., Benczúr A. A. Primal-dual approach for directed vertex connectivity augmentation and generalizations. Proc. 16th ACM-SIAM Sympos. Discrete Algorithms (2005) (ACM-SIAM)186–194Google Scholar
• Vornberger O. Easy and hard cycle covers. (1980) . Preprint, Universität Paderborn, GermanyGoogle Scholar