Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Morse, Gregory, Kozsik, Tamás
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms 05C85 (Primary) 68R10, 68Q25 (Secondary) 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

Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs
by: Morse, Gregory, et al.
Published: (2026)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

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)

Traffic-Oblivious Multi-Commodity Flow Network Design
by: Chimani, Markus, et al.
Published: (2025)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

A $4/3$ Approximation for $2$-Vertex-Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2023)

On the twin-width of near-regular graphs
by: Heinrich, Irene, et al.
Published: (2025)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

Quantum Search without Global Diffusion
by: Burke, John, et al.
Published: (2026)

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

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

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

An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets
by: Mundhra, S.
Published: (2025)

A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions
by: Morse, Gregory, et al.
Published: (2024)

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

Shortest two disjoint paths in conservative graphs
by: Schlotter, Ildikó
Published: (2023)

A Constant-factor Approximation for Weighted Bond Cover
by: Kim, Eun Jung, et al.
Published: (2021)

Low Recourse Arborescence Forests Under Uniformly Random Arcs
by: Dahlmeier, J Niklas, et al.
Published: (2025)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

Experimental algorithms for the dualization problem
by: Mezzini, Mauro, et al.
Published: (2025)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
by: Bampis, Evripidis, et al.
Published: (2024)

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

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

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

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
by: Atherton, William, et al.
Published: (2024)

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

Overlapping Biclustering
by: Bentert, Matthias, et al.
Published: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
by: Kullmann, Oliver, et al.
Published: (2026)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
by: Krishnaswamy, Ravishankar, et al.
Published: (2014)

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

On the Average-Case Performance of Greedy for Maximum Coverage
by: Balkanski, Eric, et al.
Published: (2026)

Searching in trees with monotonic query times
by: Dereniowski, Dariusz, et al.
Published: (2024)

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

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

Identification to Subclasses of Chordal Graphs
by: Golovach, Petr A., et al.
Published: (2026)

Testing forbidden order-pattern properties on hypergrids
by: Chandramouleeswaran, Harish, et al.
Published: (2025)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

Maximum Matchings in Geometric Intersection Graphs
by: Bonnet, Édouard, et al.
Published: (2019)

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
by: Chimani, Markus, et al.
Published: (2023)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)