Efficient Algorithms for the Inverse Spanning-Tree Problem

References

• Ahuja R. K., Orlin J. B. A faster algorithm for the inverse spanning tree problem. J. Algorithms (2000) 34:177–193Crossref, Google Scholar
• Ahuja R. K., Hochbaum D. S., Orlin J. B., Cornuejols G., Burkard R. E., Woeginger G. J. Solving the convex cost integer dual network flow problem. Proc. IPCO&99. Lecture Notes in Computer Science (1999a) 1610:31–44ForthcomingCrossref, Google Scholar
• Ahuja R. K., Hochbaum D. S., Orlin J. B. A cut based algorithm for the convex dual of the minimum cost network flow problem. (1999b) . Manuscript, University of California, Berkeley, CAGoogle Scholar
• Ahuja R. K., Orlin J. B., Stein C., Tarjan R. E. Improved algorithms for bipartite network flow. SIAM J. Comput. (1994) 23:906–933Crossref, Google Scholar
• Barlow R. E., Bartholomew D. J., Bremer J. M., Brunk H. D.Statistical Inference Under Order Restrictions (1972) (Wiley, New York) Google Scholar
• Dinic E. A. Algorithm for solution of a problem of maximal flow in a network with power estimation. Soviet Math. Dokl. (1970) 11:1277–1280Google Scholar
• Even S., Tarjan R. E. Network flow and testing graph connectivity. SIAM J. Comput. (1975) 4:507–518Crossref, Google Scholar
• Gallo G., Grigoriadis M. D., Tarjan R. E. A fast parametric maximum flow algorithm and applications. SIAM J. Comput. (1989) 18:30–55Crossref, Google Scholar
• Goldberg A. V., Tarjan R. E. A new approach to the maximum flow problem. J. ACM (1988) 35:921–940Crossref, Google Scholar
• Gusfield D., Martel C., Fernandez-Baca D. Fast algorithms for bipartite network flow. SIAM J. Comput. (1987) 16:237–251Crossref, Google Scholar
• Hochbaum D. S. Lower and upper bounds for allocation problems. Math. Oper. Res. (1994) 19:390–409Link, Google Scholar
• Hochbaum D. S. The pseudoflow algorithm for the maximum flow problem. (1997) . Manuscript, University of California, Berkeley, CAGoogle Scholar
• Hochbaum D. S., Queyranne M. The convex cost closure problem. SIAM J. Discrete Math. (2003) 16:192–207Crossref, Google Scholar
• Hochbaum D. S., Shanthikumar J. G. Convex separable optimization is not much harder than linear optimization. J. ACM (1990) 37:843–862Crossref, Google Scholar
• Picard J. C. Maximal closure of a graph and applications to combinatorial problems. Management Sci. (1976) 22:1268–1272Link, Google Scholar
• Sleator D. D., Tarjan R. E. A data structure for dynamic trees. J. Comput. Systems Sci. (1983) 24:362–391Crossref, Google Scholar
• Sokkalingam P. T., Ahuja R., Orlin J. B. Solving inverse spanning tree problems through network flow techniques. Oper. Res. (1999) 47:291–298Link, Google Scholar
• Tarantola A.Inverse Problem Theory: Methods for Data Fitting and Model Parameter Estimation (1987) (Elsevier, Amsterdam The Netherlands) Google Scholar