Single-pass streaming algorithms to partition graphs into few forests

DOI10.1007/978-3-030-89543-3_45MaRDI QIDQ2695324zbMATH OpenOpenAlexFDO

Authors Cheng-Hung Chiang, Meng-Tsung Tsai

Publication date 30 March 2023

Full work available at URL https://doi.org/10.1007/978-3-030-89543-3_45

zbMATH Keywords

arboricitydominating setgreedyorientationthickness

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A constructive arboricity approximation scheme
• A data structure for dynamic trees
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
• Computing the degeneracy of large graphs
• Data streams: algorithms and applications.
• Decomposition of Finite Graphs Into Forests
• Densest subgraph in dynamic graph streams
• Forests, frames, and games: Algorithms for matroid sums and applications
• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• scientific article; zbMATH DE number 7650919 (Why is no real title available?)
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Minimum dominating set approximation in graphs of bounded arboricity
• Single pass spectral sparsification in dynamic streams
• Sparsification—a technique for speeding up dynamic graph algorithms
• Sublinear algorithms for ( + 1) vertex coloring
• The point-arboricity of a graph
• The Probabilistic Communication Complexity of Set Intersection
• Tight Approximations of Degeneracy in Large Graphs

Cited in

(1)

• Partitioning technique for transforming perfect binary trees into single-row networks

This page was built for publication: Single-pass streaming algorithms to partition graphs into few forests

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