Matchings in Node-Weighted Convex Bipartite Graphs

References

• Ahuja R. K., Orlin J. B. A faster algorithm for the inverse spanning tree problem. J. Algorithms (2000) 34(1):177–193Crossref, Google Scholar
• Brodal G. S., Lagogiannis G., Makris C., Tsakalidis A., Tsichlas K. Optimal finger search trees in the pointer machine. J. Comput. System Sci., Special Issue on STOC 2002 (2003) 67(2):381–418Google Scholar
• Campêlo M. B., Klein S. Maximum vertex-weighted matching in strongly chordal graphs. Discrete Appl. Math. (1998) 84(1–3):71–77Crossref, Google Scholar
• Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions. J. Symbolic Comput. (1990) 9(3):251–280Crossref, Google Scholar
• Edmonds J., Karp R. M. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (1972) 19(2):248–264Crossref, Google Scholar
• Gabow H. N., Tarjan R. E. A linear-time algorithm for a special case of disjoint set union. J. Comput. System Sci. (1985) 30(2):209–21Crossref, Google Scholar
• Gallo G. An O(n log n) algorithm for the convex bipartite matching problem. Oper. Res. Lett. (1984) 3(1):31–34Crossref, Google Scholar
• Glover F. Maximum matching in convex bipartite graphs. Naval Res. Logist. Quart. (1967) 14:313–316Crossref, Google Scholar
• Lipski W., Preparata F. P. Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica (1981) 15:329–346Crossref, Google Scholar
• Sankowski P. Weighted bipartite matching in matrix multiplication time. ICALP (1), Lecture Notes in Computer Science (2006) 4051(Springer-Verlag, Berlin) 274–285Crossref, Google Scholar
• Scutella M. G., Scevola G. A modification of Lipski-Preparata's algorithm for the maximum matching problem on bipartite convex graphs. Ricerca Operativa (1988) 46:63–77Google Scholar
• Steiner G., Yeomans J. S. A linear time algorithm for determining maximum matchings in convex, bipartite graphs. Comput. Math. Appl. (1996) 31(12):91–96Crossref, Google Scholar