article

Free access

The complexity of restricted spanning tree problems

Authors:

Christos H. Papadimitriou,

Mihalis YannakakisAuthors Info & Claims

Journal of the ACM (JACM), Volume 29, Issue 2

Pages 285 - 309

https://doi.org/10.1145/322307.322309

Published: 01 April 1982 Publication History

PDF eReader

References

[1]

AHO, A V, HOPCROFT, J E, AND ULLMAN, J D The Design and Analysts of Computer Algorithms Addison-Wesley, Reading, Mass, 1974

Crossref

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

Crossref

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.

Crossref

Google Scholar

[7]

JOHNSON, D.S., AND LIN, S Private communicat,on, Feb. 1976

Google 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-103

Google 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

Crossref

Google Scholar

[16]

PAPADIMITRIOU, C H, AND YANNAKAKIS, M Unpubhshed manuscript, 1977

Google 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.

Crossref

Google Scholar

Cited By

View all

Zhou ZLi S(2025) On the -index of graphs with given order and dissociation number Discrete Applied Mathematics10.1016/j.dam.2024.09.002360(167-180)Online publication date: Jan-2025
https://doi.org/10.1016/j.dam.2024.09.002
Araujo JDourado MProtti FSampaio R(2025)The iteration time and the general position number in graph convexitiesApplied Mathematics and Computation10.1016/j.amc.2024.129084487(129084)Online publication date: Feb-2025
https://doi.org/10.1016/j.amc.2024.129084
Benedek MBiró PCsáji GJohnson MPaulusma DYe XDastani MSichman JAlechina NDignum V(2024)Computing Balanced Solutions for Large International Kidney Exchange Schemes when Cycle Length is UnboundedProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663091(2153-2155)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663091
Show More Cited By

Index Terms

The complexity of restricted spanning tree problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness

Recommendations

Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Abstract
Inspired 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 ... $_{}$ $_{}$ $_{}$ $_{} \sqrt{}$ $_{}$ $_{}$ $_{}$ $_{} \sqrt{}$ $_{} \sqrt{}$ $_{} \sqrt{}$ $_{} \sqrt{}$
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 = (d_ij)ⁿ_i,j=1 be a length metric. For a tree T denote by d_T(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, D_T, is the maximum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 29, Issue 2

April 1982

330 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322307

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1982

Published in JACM Volume 29, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

155
Total Citations
View Citations
1,752
Total Downloads

Downloads (Last 12 months)240
Downloads (Last 6 weeks)18

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhou ZLi S(2025) On the -index of graphs with given order and dissociation number Discrete Applied Mathematics10.1016/j.dam.2024.09.002360(167-180)Online publication date: Jan-2025
https://doi.org/10.1016/j.dam.2024.09.002
Araujo JDourado MProtti FSampaio R(2025)The iteration time and the general position number in graph convexitiesApplied Mathematics and Computation10.1016/j.amc.2024.129084487(129084)Online publication date: Feb-2025
https://doi.org/10.1016/j.amc.2024.129084
Benedek MBiró PCsáji GJohnson MPaulusma DYe XDastani MSichman JAlechina NDignum V(2024)Computing Balanced Solutions for Large International Kidney Exchange Schemes when Cycle Length is UnboundedProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663091(2153-2155)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663091
Thilikos DWiederrecht S(2024)Killing a VortexJournal of the ACM10.1145/366464871:4(1-56)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3664648
Eisenbrand FRohwedder LWęgrzycki K(2024)Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00100(1610-1620)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00100
Fomin FFraigniaud PGolovach P(2024)Parameterized complexity of broadcasting in graphsTheoretical Computer Science10.1016/j.tcs.2024.114508997:COnline publication date: 27-May-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114508
Gourvès LHarutyunyan ALampis MMelissinos N(2024)Filling crosswords is very hardTheoretical Computer Science10.1016/j.tcs.2023.114275982(114275)Online publication date: Jan-2024
https://doi.org/10.1016/j.tcs.2023.114275
Huang JGeng XLi SZhou Z(2024)On spectral extrema of graphs with given order and dissociation numberDiscrete Applied Mathematics10.1016/j.dam.2023.10.001342(368-380)Online publication date: Jan-2024
https://doi.org/10.1016/j.dam.2023.10.001
Huang JZhang H(2024)Extremal vertex-degree function index with given order and dissociation numberDiscrete Applied Mathematics10.1016/j.dam.2023.09.005342(142-152)Online publication date: Jan-2024
https://doi.org/10.1016/j.dam.2023.09.005
Chu YLuo JZheng T(2024)Stable Matching with Approval Preferences Under Partial InformationAlgorithmic Aspects in Information and Management10.1007/978-981-97-7801-0_6(64-75)Online publication date: 21-Sep-2024
https://dl.acm.org/doi/10.1007/978-981-97-7801-0_6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios

Tree insertion grammar: a cubic-time, parsable formalism that lexicalizes context-free grammar without changing the trees produced

Minimum restricted diameter spanning trees

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations