scientific article; zbMATH DE number 7650919

DOI10.4230/LIPICS.STACS.2020.34MaRDI QIDQ5874307zbMATH OpenFDO

Authors Yi-Jun Chang, Martin Farach-Colton, Tsan-sheng Hsu, Meng-Tsung Tsai

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/2001.07672

zbMATH Keywords

BFS treesDFS treesmax-leaf spanning trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(7)

• A greedy algorithm for finding maximum spanning trees in infinite graphs
• Single-pass streaming algorithms to partition graphs into few forests
• Complexity of computation of a spanning tree enumeration algorithm
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• On the complexity of finding 1-center spanning trees
• Constructing long paths in graph streams
• Almost optimal superconstant-pass streaming lower bounds for reachability

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874307)