Space limited linear-time graph algorithms on big data

DOI10.1016/J.TCS.2024.114468MaRDI QIDQ6196840zbMATH OpenFDO

Authors

Publication date 15 March 2024

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

zbMATH Keywords

streaming algorithmbig datavertex coveredge dominating setmaximal matchingkernelization algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Communication complexity (for algorithm designers)
• Data streams: algorithms and applications.
• Faster Update Time for Turnstile Streaming Algorithms
• Introduction to algorithms.
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Kernelization. Theory of parameterized preprocessing
• Kernels for edge dominating set: simpler or smaller
• New parameterized algorithms for the edge dominating set problem
• On randomized one-round communication complexity
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Parameterized algorithms
• Streaming kernelization
• Time lower bounds for nonadaptive turnstile streaming algorithms
• Vertex cover: Further observations and further improvements
• Vertex packings: Structural properties and algorithms
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(1)

• Nearly time-optimal kernelization algorithms for the line-cover problem with big data

This page was built for publication: Space limited linear-time graph algorithms on big data

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