Cover Image

Lower Bounds on Tree Covers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Yu, Tan, Zihan, Xu, Hangyu
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lower Bounds on $0$-Extension with Steiner Nodes
by: Chen, Yu, et al.
Published: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
by: Jin, Billy, et al.
Published: (2023)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
by: Chen, Yu, et al.
Published: (2024)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
by: Chen, Yu, et al.
Published: (2023)

Paths and Intersections: Exact Emulators for Planar Graphs
by: Li, George Z., et al.
Published: (2025)

Forest Covers and Bounded Forest Covers
by: Gaur, Daya Ram, et al.
Published: (2024)

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

Lower bounds on collective additive spanners
by: Corneil, Derek G., et al.
Published: (2025)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
by: Gutekunst, Samuel C.
Published: (2025)

Lower bounds for graph reconstruction with maximal independent set queries
by: Michel, Lukas, et al.
Published: (2024)

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

Optimising Cylindrical Algebraic Coverings for use in SMT by Solving a Set Covering Problem with Reasons
by: Babatunde, Abiola, et al.
Published: (2026)

Cover time of random subgraphs of the hypercube
by: Cooper, Colin, et al.
Published: (2025)

Optimal Bounds for Open Addressing Without Reordering
by: Farach-Colton, Martin, et al.
Published: (2025)

Triangle-Covered Graphs: Algorithms, Complexity, and Structure
by: Madani, Amirali, et al.
Published: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
by: Bodwin, Greg, et al.
Published: (2026)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
by: Kuszmaul, William
Published: (2025)

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
by: Con, Roni, et al.
Published: (2024)

A faster algorithm for Vertex Cover parameterized by solution size
by: Harris, David G., et al.
Published: (2022)

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

Succinct Encodings of Binary Trees with Application to AVL Trees
by: Chizewer, Jeremy, et al.
Published: (2023)

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
by: Guo, Zeyu, et al.
Published: (2023)

Counting Permutation Patterns with Multidimensional Trees
by: Beniamini, Gal, et al.
Published: (2024)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

Fast Rational Search via Stern-Brocot Tree
by: Weyers, Connor, et al.
Published: (2025)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
by: Bai, Yuhang, et al.
Published: (2026)

Lower Bounds for Leaf Rank of Leaf Powers
by: Høgemo, Svein
Published: (2024)

Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
by: Karamchedu, Mithra, et al.
Published: (2025)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
by: Korhonen, Tuukka
Published: (2024)

Matroid Intersection under Minimum Rank Oracle
by: Bárász, Mihály, et al.
Published: (2024)

An Improved Bound for the Beck-Fiala Conjecture
by: Bansal, Nikhil, et al.
Published: (2025)

Tight Bounds for Sparsifying Random CSPs
by: Brakensiek, Joshua, et al.
Published: (2025)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

Query Complexity of the Metric Steiner Tree Problem
by: Chen, Yu, et al.
Published: (2022)

Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
by: Alrabiah, Omar, et al.
Published: (2023)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
by: Bakshi, Ainesh, et al.
Published: (2026)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
by: Chen, Yu, et al.
Published: (2024)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)