Sublinear-time reductions for big data computing

DOI10.1007/978-3-030-92681-6_30OpenAlexW4205594610MaRDI QIDQ5918726

Xiang-Yu Gao, Jian-Zhong Li, Dongjing Miao

Publication date: 29 June 2022

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

preprocessingreduction techniquesbig data computingsublinear-time tractability

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Unnamed Item
• Depth-first search is inherently sequential
• Preprocessing of intractable problems
• Sorted Range Reporting
• A taxonomy of problems with fast parallel algorithms
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
• Fine-Grained Complexity Theory (Tutorial)
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Recognizing the tractability in big data computing

This page was built for publication: Sublinear-time reductions for big data computing