Parameterized streaming algorithms for topological sorting

DOI10.4230/LIPICS.WADS.2025.18MaRDI QIDQ7312567zbMATH OpenFDO

Authors Ho-Lin Chen, Peng-Ting Lin, Meng-Tsung Tsai

Publication date 11 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.WADS.2025.18

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites work

• A decomposition theorem for partially ordered sets
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Data Streams: Algorithms and Applications
• Faster and unified algorithms for diameter reducing shortcuts and minimum chain covers
• scientific article; zbMATH DE number 7650305 (Why is no real title available?)
• Meta-theorems for parameterized streaming algorithms
• Minimum chain cover in almost linear time
• New problems complete for nondeterministic log space
• On graph problems in a semi-streaming model
• On the independence number of random graphs
• Parameterized complexity of streaming diameter and connectivity problems
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Set reconciliation with nearly optimal communication complexity
• Space-bounded reducibility among combinatorial problems
• Streaming kernelization
• The mathematics of Paul Erdős II
• Towards a theory of parameterized streaming algorithms
• Vertex Ordering Problems in Directed Graph Streams

This page was built for publication: Parameterized streaming algorithms for topological sorting

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