Cover Image

The Complexity Landscape of Dynamic Distributed Subgraph Finding

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chang, Yi-Jun, Chen, Lyuting, Chen, Yanyu, Mishra, Gopinath, Yang, Mingyang
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
by: Chang, Yi-Jun, et al.
Published: (2024)

Optimal Distributed Replacement Paths
by: Chang, Yi-Jun, et al.
Published: (2025)

Finding Small Complete Subgraphs Efficiently
by: Chen, Ke, et al.
Published: (2023)

Finding Order-Preserving Subgraphs
by: Imamura, Haruya, et al.
Published: (2025)

A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model
by: Chang, Yi-Jun, et al.
Published: (2023)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

On Parallel $k$-Center Clustering
by: Coy, Sam, et al.
Published: (2023)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
by: Bishnu, Arijit, et al.
Published: (2025)

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

Finding Induced Subgraphs from Graphs with Small Mim-Width
by: Otachi, Yota, et al.
Published: (2024)

Distributed Subgraph Finding: Progress and Challenges
by: Censor-Hillel, Keren
Published: (2022)

Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
by: Hanaka, Tesshu, et al.
Published: (2025)

Packing Compact Subgraphs with Applications to Districting
by: Chen, Ho-Lin, et al.
Published: (2026)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
by: Bishnu, Arijit, et al.
Published: (2024)

Log Diameter Rounds MST Verification and Sensitivity in MPC
by: Coy, Sam, et al.
Published: (2024)

Optimal (degree+1)-Coloring in Congested Clique
by: Coy, Sam, et al.
Published: (2023)

Parallel Derandomization for Coloring
by: Coy, Sam, et al.
Published: (2023)

Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models
by: Bishnu, Arijit, et al.
Published: (2025)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
by: Dey, Palash, et al.
Published: (2026)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
by: Norose, Ryoma, et al.
Published: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Scalable Algorithm for Finding Balanced Subgraphs with Tolerance in Signed Networks
by: Chen, Jingbang, et al.
Published: (2024)

Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
by: Long, Yaowei, et al.
Published: (2024)

Round and Communication Efficient Graph Coloring
by: Chang, Yi-Jun, et al.
Published: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

The Parameterized Complexity Landscape of the Unsplittable Flow Problem
by: Ganian, Robert, et al.
Published: (2024)

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
by: Chakraborty, Sourav, et al.
Published: (2024)

Destroying Densest Subgraphs is Hard
by: Bazgan, Cristina, et al.
Published: (2024)

Forbidden Subgraph Problems with Predictions
by: Böckenhauer, Hans-Joachim, et al.
Published: (2025)

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
by: Zhou, Yi, et al.
Published: (2025)

In-depth Analysis of Densest Subgraph Discovery in a Unified Framework
by: Zhou, Yingli, et al.
Published: (2024)

Parameterized Complexity of Finding Dissimilar Shortest Paths
by: Funayama, Ryo, et al.
Published: (2024)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

On the Complexity of Finding Approximate LCS of Multiple Strings
by: Hasibi, Hamed, et al.
Published: (2025)

Counting Cohesive Subgraphs with Hereditary Properties
by: Li, Rong-Hua, et al.
Published: (2024)

Subexponential Parameterized Algorithms for Hitting Subgraphs
by: Lokshtanov, Daniel, et al.
Published: (2024)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
by: Çivril, Ali
Published: (2023)

Scalable $k$-clique Densest Subgraph Search
by: Ye, Xiaowei, et al.
Published: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries
by: Kothalawala, Buddhi, et al.
Published: (2026)