Cover Image

Fully Dynamic Strongly Connected Components in Planar Digraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Karczmarz, Adam, Smulewicz, Marcin
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

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Fully Dynamic Algorithms for Transitive Reduction
by: Goranci, Gramoz, et al.
Published: (2025)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Node-Weighted Multicut in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2026)

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
by: Karczmarz, Adam, et al.
Published: (2024)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Simple Algorithms for Fully Dynamic Edge Connectivity
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Incremental Strongly Connected Components with Predictions
by: Deng, Ronald, et al.
Published: (2026)

Towards Scalable and Practical Batch-Dynamic Connectivity
by: De Man, Quinten, et al.
Published: (2024)

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

Approximation Schemes for Planar Graph Connectivity Problems
by: Neuwohner, Meike, et al.
Published: (2025)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Stochastic Embedding of Digraphs into DAGs
by: Filtser, Arnold
Published: (2025)

Approximation Algorithms for Digraph Width Parameters
by: Kintali, Shiva, et al.
Published: (2011)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

Graph Reconstruction with a Connected Components Oracle
by: Harviainen, Juha, et al.
Published: (2025)

On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
by: Blažej, Václav, et al.
Published: (2024)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Linear Kernels for $l$-Exact Component Order Connectivity
by: Liu, Yuxi, et al.
Published: (2026)

Reconfiguring Multiple Connected Components with Size Multiset Constraints
by: Nakahata, Yu
Published: (2025)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, et al.
Published: (2025)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
by: Włodarczyk, Michał
Published: (2024)

Integer and Unsplittable Multiflows in Series-Parallel Digraphs
by: Almoghrabi, Mohammed Majthoub, et al.
Published: (2024)

Fully Dynamic Euclidean k-Means
by: Bhattacharya, Sayan, et al.
Published: (2025)

Fully Dynamic Algorithms for Chamfer Distance
by: Goranci, Gramoz, et al.
Published: (2025)

Fully Dynamic Spectral Sparsification of Hypergraphs
by: Goranci, Gramoz, et al.
Published: (2025)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
by: Kumar, Mithilesh, et al.
Published: (2016)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
by: Forster, Sebastian, et al.
Published: (2025)

Fully-Dynamic Submodular Cover with Bounded Recourse
by: Gupta, Anupam, et al.
Published: (2020)

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
by: Behnezhad, Soheil, et al.
Published: (2024)

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
by: Zhao, Yibin
Published: (2025)

Compressing Dynamic Fully Indexable Dictionaries in Word-RAM
by: Domingues, Gabriel Marques
Published: (2026)