Space limited linear-time graph algorithms on big data

DOI10.1016/J.TCS.2024.114468MaRDI QIDQ6196840FDOQ6196840

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

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