Cover Image

Above-Guarantee Algorithm for Properly Colored Spanning Trees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bai, Yuhang, Bérczi, Kristóf
Format:	Preprint
Published:	2026
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

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

Approximating maximum-size properly colored forests
by: Bai, Yuhang, et al.
Published: (2024)

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

Approximating maximum properly colored forests via degree bounded independent sets
by: Bai, Yuhang, et al.
Published: (2025)

Rainbow Arborescence Conjecture
by: Bérczi, Kristóf, et al.
Published: (2024)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
by: Norose, Ryoma, et al.
Published: (2024)

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

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
by: Dhawan, Abhishek
Published: (2024)

Finding the diameter of a tree with distance queries
by: Gerbner, Dániel, et al.
Published: (2025)

Sampling Colorings with Fixed Color Class Sizes
by: Kuchukova, Aiya, et al.
Published: (2026)

Multiway Cuts with a Choice of Representatives
by: Bérczi, Kristóf, et al.
Published: (2024)

Matroid Secretary via Labeling Schemes
by: Bérczi, Kristóf, et al.
Published: (2024)

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

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
by: Dhawan, Abhishek
Published: (2024)

A Note on Generic Tangle Algorithms
by: Elbracht, Christian, et al.
Published: (2020)

Parameterized Algorithms for Diversity of Networks with Ecological Dependencies
by: Jones, Mark, et al.
Published: (2025)

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

Complexity and Algorithm for the Matching vertex-cutset Problem
by: Li, Hengzhe, et al.
Published: (2025)

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
by: Haviv, Ishay
Published: (2022)

Free-order secretary for two-sided independence systems
by: Bérczi, Kristóf, et al.
Published: (2025)

$\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions
by: Bérczi, Kristóf, et al.
Published: (2025)

Algorithmic study on liar's vertex-edge domination problem
by: Bhattacharya, Debojyoti, et al.
Published: (2023)

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

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

A Faster Deterministic Approximation Algorithm for TTP-2
by: Kanaya, Yuga, et al.
Published: (2023)

Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
by: Gavva, Surya Teja, et al.
Published: (2025)

A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications
by: Dumitrescu, Adrian
Published: (2024)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
by: Murakami, Hitoshi, et al.
Published: (2024)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
by: Kano, Takumi, et al.
Published: (2026)

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

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
by: Gutin, Gregory, et al.
Published: (2022)

Lower Bounds on Tree Covers
by: Chen, Yu, et al.
Published: (2025)

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)

Inverse matroid optimization under subset constraints
by: Bérczi, Kristóf, et al.
Published: (2025)

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
by: Bérczi, Kristóf, et al.
Published: (2024)

Splitting-off in Hypergraphs
by: Bérczi, Kristóf, et al.
Published: (2023)

Analysis of a Random Local Search Algorithm for Dominating Set
by: Higl, Hendrik
Published: (2026)

Online Coloring of Short Intervals
by: Chybowska-Sokół, Joanna, et al.
Published: (2018)