Cover Image

Emit As You Go: Enumerating Edges of a Spanning Tree

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Casel, Katrin, Neubert, Stefan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fine-Grained Complexity of Regular Path Queries
by: Casel, Katrin, et al.
Published: (2021)

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

The Complexity of Maximal Common Subsequence Enumeration
by: Buzzega, Giovanni, et al.
Published: (2025)

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

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

Enumerating models of DNF faster: breaking the dependency on the formula size
by: Capelli, Florent, et al.
Published: (2018)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
by: Frei, Fabian, et al.
Published: (2024)

Complexity of Finding and Enumerating Interconnection Trees
by: Demange, Noé, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
by: Jonsson, Peter, et al.
Published: (2025)

Can You Link Up With Treewidth?
by: Curticapean, Radu, et al.
Published: (2024)

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
by: Hanaka, Tesshu, et al.
Published: (2023)

Spanning Trees Minimizing Branching Costs
by: Gargano, Luisa, et al.
Published: (2024)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

Enumeration of minimal transversals of hypergraphs of bounded VC-dimension
by: Mary, Arnaud
Published: (2024)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
by: Balzereit, Kaja, et al.
Published: (2024)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
by: Asadi, Vahid R., et al.
Published: (2026)

Enumeration and updates for conjunctive linear algebra queries through expressibility
by: Muñoz, Thomas, et al.
Published: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
by: de Berg, Mark, et al.
Published: (2025)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
by: Grandjean, Étienne, et al.
Published: (2025)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
by: Oka, Keigo, et al.
Published: (2026)

A lossless a priori splitting rule for split-delivery routing problems
by: Jones, Bo, et al.
Published: (2025)

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

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
by: Bendotti, Pascale, et al.
Published: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
by: Maalouly, Nicolas El, et al.
Published: (2025)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)