Image de couverture de livre

Two Complexity Results on Spanning-Tree Congestion Problems

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Atalig, Sunny, Chrobak, Marek, Dürr, Christoph, Kolman, Petr, Luu, Huong, Sgall, Jiří, Zhu, Gregory
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
par: Atalig, Sunny, et autres
Publié: (2025)

Approximation of Spanning Tree Congestion using Hereditary Bisection
par: Kolman, Petr
Publié: (2024)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
par: Atalig, Sunny, et autres
Publié: (2024)

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
par: Basiak, Mateusz, et autres
Publié: (2025)

Speed-robust scheduling revisited
par: Minařík, Josef, et autres
Publié: (2024)

Improved online load balancing with known makespan
par: Böhm, Martin, et autres
Publié: (2024)

Min-Max Connected Multiway Cut
par: Tiwary, Hans Raj, et autres
Publié: (2026)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
par: Kuschner, Jordan, et autres
Publié: (2024)

On HTLC-Based Protocols for Multi-Party Cross-Chain Swaps
par: Clark, Emily, et autres
Publié: (2024)

Scenario-Based Robust Optimization of Tree Structures
par: Angelopoulos, Spyros, et autres
Publié: (2024)

Fast Spanning Tree Sampling in Broadcast Congested Clique
par: Anari, Nima, et autres
Publié: (2026)

Polynomial Kernels for Spanning Tree with Diversity Requirements
par: Golovach, Petr A., et autres
Publié: (2026)

Online Disjoint Spanning Trees and Polymatroid Bases
par: Chandrasekaran, Karthekeyan, et autres
Publié: (2025)

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
par: Dürr, Anita
Publié: (2022)

Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds
par: Dürr, Christoph, et autres
Publié: (2024)

Planar Length-Constrained Minimum Spanning Trees
par: Hershkowitz, D Ellis, et autres
Publié: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
par: Elkin, Michael, et autres
Publié: (2025)

Simple Length-Constrained Minimum Spanning Trees
par: Hershkowitz, D Ellis, et autres
Publié: (2024)

Budget and Profit Approximations for Spanning Tree Interdiction
par: Ostrovsky, Rafail, et autres
Publié: (2025)

A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
par: Neuwohner, Meike
Publié: (2024)

Online Computation with Untrusted Advice
par: Angelopoulos, Spyros, et autres
Publié: (2019)

Dynamic Parameterized Feedback Problems in Tournaments
par: Zych-Pawlewicz, Anna, et autres
Publié: (2024)

Enumerating All Directed Spanning Trees in Optimal Time
par: Gawrychowski, Paweł, et autres
Publié: (2026)

Stochastic Minimum Spanning Trees with a Single Sample
par: Hoeksma, Ruben, et autres
Publié: (2024)

Query Complexity of the Metric Steiner Tree Problem
par: Chen, Yu, et autres
Publié: (2022)

The Two-Center Problem of Uncertain Points on Trees
par: Xu, Haitao, et autres
Publié: (2024)

Congestion-Approximators from the Bottom Up
par: Li, Jason, et autres
Publié: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
par: Peng, Pan, et autres
Publié: (2026)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
par: Azarmehr, Amir, et autres
Publié: (2024)

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
par: Shen, Fangjian, et autres
Publié: (2025)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
par: Liu, Yang P., et autres
Publié: (2025)

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
par: Angelopoulos, Spyros, et autres
Publié: (2025)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
par: Bringmann, Karl, et autres
Publié: (2026)

Faster algorithms for k-Orthogonal Vectors in low dimension
par: Dürr, Anita, et autres
Publié: (2025)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
par: Bringmann, Karl, et autres
Publié: (2024)

Finding Spanning Trees with Perfect Matchings
par: Bérczi, Kristóf, et autres
Publié: (2024)

Optimal (degree+1)-Coloring in Congested Clique
par: Coy, Sam, et autres
Publié: (2023)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
par: Ding, Xiangyun, et autres
Publié: (2025)

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

The Planted Spanning Tree Problem
par: Moharrami, Mehrdad, et autres
Publié: (2025)