Cover Image

DAG Scheduling in the BSP Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Papp, Pál András, Anegg, Georg, Yzelman, A. N.
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity 68Q17, 68Q85, 05C20 G.2.2; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

The Impact of Partial Computations on the Red-Blue Pebble Game
by: Papp, Pál András, et al.
Published: (2025)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
by: Lobe, Elisabeth, et al.
Published: (2021)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
by: Huber, Michael Kiran
Published: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
by: Philip, Geevarghese, et al.
Published: (2026)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

A New Temporal Interpretation of Cluster Editing
by: Bocci, Cristiano, et al.
Published: (2022)

Approaching I/O-optimality for Approximate Attention
by: Papp, Pál András, et al.
Published: (2026)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

The Gallai Vertex Problem is $Θ_2^p$-Complete
by: Nikabadi, Amir, et al.
Published: (2026)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
by: Haslebacher, Sebastian
Published: (2025)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
by: Golovach, Petr A., et al.
Published: (2022)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
by: Liao, Chao, et al.
Published: (2022)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

Steiner Tree Parameterized by Multiway Cut and Even Less
by: Jansen, Bart M. P., et al.
Published: (2024)

XALP-completeness of Parameterized Problems on Planar Graphs
by: Bodlaender, Hans L., et al.
Published: (2024)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
by: Lubiw, Anna, et al.
Published: (2025)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
by: DasGupta, Bhaskar, et al.
Published: (2026)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
by: Phillips, Reed
Published: (2026)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Graphs whose vertices of degree at least 2 lie in a triangle
by: Forte, Vinicius L. do, et al.
Published: (2022)

Computing shortest closed curves on non-orientable surfaces
by: Bulavka, Denys, et al.
Published: (2024)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2024)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

Amnesiac Flooding: Easy to break, hard to escape
by: Austin, Henry, et al.
Published: (2025)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)