Christos H. Papadimitriou
- 1 AHO, A V, HOPCROFT, J E, AND ULLMAN, J D The Design and Analysts of Computer Algorithms Addison-Wesley, Reading, Mass, 1974 Google Scholar
- 2 EDMONDS, J. Paths, trees, and flowers Canad J Math 17 (1965), 449--467.Google Scholar
- 3 EDMONDS, J.Submodular funcuons, matrolds and certain polyhedra, lrt Combinatorial Structures and Thelr Apphcatwns, Proc. of the Calgary fnternauonal Conference, R Guy, Ed., Gordon and Breach, N.Y., 1970, pp. 69-87.Google Scholar
- 4 EDMONDS, J Matrolds and the greedy algorithm. Math. Prog 1 (1971), 127-136.Google Scholar
- 5 GAREY, M.R., AND JOIINSON, D S Computers and lntractabdrty: A Guide to the Theory of NP- Completeness. Freeman, San Francisco, 1979 Google Scholar
- 6 ITAI, A., RODEH, M, AND TANIMOTO, S.L. Some matching problems for bipartite graphs J A CM 25, 4 (Oct. 1978), 517-525. Google Scholar
- 7 JOHNSON, D.S., AND LIN, S Private communicat,on, Feb. 1976Google Scholar
- 8 KARP, R M. Reductbdlty among combmatonal problems. In Complexlty of Computer Computations, R. E. Mdler and J W. Thatcher, Eds., Plenum, New York, 1972, pp 85-103Google Scholar
- 9 KRUSKAL, J B On the shortest spanning subtree of the graph and the traveling salesman problem. Proc Am Math. Soc. 2 (1956), 48-50.Google Scholar
- 10 LAWLER, E.L. Matrold intersection algonth_ms Math Prog 9 (1975), 31-56.Google Scholar
- 11 LAWLER, E L Combinatorial Optimization Networks and Matroids. Holt-Rhinehart-Wmston, 1977.Google Scholar
- 12 LIN, S. Private commumcatmn, Feb. 1976.Google Scholar
- 13 LOVASZ, LThe matrold panty problem Unpubhshed manuscript, Umverstty of Waterloo, Waterloo, Ontario, 1979.Google Scholar
- 14 Pm'aD~a'rmOV, C.H. The complexity of the capacltated tree problem Networks 8, 3 (1978), 217-230.Google Scholar
- 15 PAPADIMITRIOU, C.H., AND STEIGLITZ, K Combmatorzal Optimization Algorithms. Prentice-Hall, Englewood Cliffs, N J, 1982 Google Scholar
- 16 PAPADIMITRIOU, C H, AND YANNAKAKIS, M Unpubhshed manuscript, 1977Google Scholar
- 17 PRIM, R.C. Shortest ~ormecuon networks and some generahzations Bell Syst Teeh. J. 36 (1957), 1389-1401.Google Scholar
- 18 YANNAKAKIS, M. Node- and edge-deletmn NP-complete problems Proc 10th Ann ACM Syrup on Theory of Computing, San Dingo, Cahf, 1978, pp. 253-265. Google Scholar
Index Terms
- The complexity of restricted spanning tree problems
Recommendations
Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
AbstractInspired by the seminal works of Khuller et al. (SIAM J. Comput. 25(2), 355–368 (1996)) and Chan (Discrete Comput. Geom. 32(2), 177–194 (2004)) we study the bottleneck version of the Euclidean bounded-degree spanning tree problem. A bottleneck ...
Tree insertion grammar: a cubic-time, parsable formalism that lexicalizes context-free grammar without changing the trees produced
Tree insertion grammar (TIG) is a tree-based formalism that makes use of tree substitution and tree adjunction. TIG is related to tree adjoining grammar. However, the adjunction permitted in TIG is sufficiently restricted that TIGs only derive context-...
Minimum restricted diameter spanning trees
Let G = (V,E) be a requirement graph. Let d = (dij)ni,j=1 be a length metric. For a tree T denote by dT(i,j) the distance between i and j in T (the length according to d of the unique i - j path in T). The restricted diameter of T, DT, is the maximum ...
Comments