The largest tree in a random graph

DOI10.1016/0304-3975(83)90034-8zbMath0512.68045OpenAlexW2019417869MaRDI QIDQ1050116

Marco Protasi, Alberto Marchetti-Spaccamela

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90034-8

zbMATH Keywords

approximate greedy algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Induced trees in sparse random graphs, On the order of the largest induced tree in a random graph, A parametric analysis of the largest induced tree problem in random graphs, Maximal induces trees in sparse random graphs, Large induced trees in sparse random graphs

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Hamiltonian circuits in random graphs
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• On colouring random graphs
• Cliques in random graphs
• `` Strong NP-Completeness Results
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item