Cover Image

Enumerating All Directed Spanning Trees in Optimal Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gawrychowski, Paweł, Knapik, Marcin
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Enumerating m-Length Walks in Directed Graphs with Constant Delay
by: Adamson, Duncan, et al.
Published: (2024)

Optimal Distance Labeling for Permutation Graphs
by: Gawrychowski, Paweł, et al.
Published: (2024)

Dynamic Longest Common Substring in Polylogarithmic Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

Optimal Bounds for Distinct Quartics
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Better Indexing for Rectangular Pattern Matching
by: Gawrychowski, Paweł, et al.
Published: (2025)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
by: Gawrychowski, Paweł, et al.
Published: (2024)

Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
by: Dudek, Bartłomiej, et al.
Published: (2020)

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
by: Gawrychowski, Paweł, et al.
Published: (2024)

Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
by: Gawrychowski, Pawel, et al.
Published: (2024)

Balancing Two-Dimensional Straight-Line Programs
by: Boneh, Itai, et al.
Published: (2025)

Faster two-dimensional pattern matching with $k$ mismatches
by: Ellert, Jonas, et al.
Published: (2024)

Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
by: Goldenfeld, Michael Elkin Tanya
Published: (2026)

Emit As You Go: Enumerating Edges of a Spanning Tree
by: Casel, Katrin, et al.
Published: (2025)

Optimal Enumeration of Eulerian Trails in Directed Graphs
by: Bals, Ben, et al.
Published: (2026)

Time-Optimal Directed q-Analysis
by: Windisch, Felix, et al.
Published: (2025)

Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries
by: Nozaki, Yuta, et al.
Published: (2024)

Local Enumeration: The Not-All-Equal Case
by: Gurumukhani, Mohit, et al.
Published: (2025)

Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
by: Conte, Alessio, et al.
Published: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

Online Disjoint Spanning Trees and Polymatroid Bases
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Planar Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
by: Elkin, Michael, et al.
Published: (2025)

Simple Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2024)

Budget and Profit Approximations for Spanning Tree Interdiction
by: Ostrovsky, Rafail, et al.
Published: (2025)

Near-Universally-Optimal Differentially Private Minimum Spanning Trees
by: Hladík, Richard, et al.
Published: (2024)

Two Complexity Results on Spanning-Tree Congestion Problems
by: Atalig, Sunny, et al.
Published: (2026)

Stochastic Minimum Spanning Trees with a Single Sample
by: Hoeksma, Ruben, et al.
Published: (2024)

Transversal Rank, Conformality and Enumeration
by: Schirneck, Martin
Published: (2026)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
by: Shen, Fangjian, et al.
Published: (2025)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
by: Liu, Yang P., et al.
Published: (2025)

Finding Spanning Trees with Perfect Matchings
by: Bérczi, Kristóf, et al.
Published: (2024)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
by: Kurita, Kazuhiro, et al.
Published: (2025)

Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
by: Jang, Jihoon, et al.
Published: (2025)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
by: Mao, Xiao
Published: (2023)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
by: Ding, Xiangyun, et al.
Published: (2025)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
by: Bonnet, Édouard, et al.
Published: (2026)