Cover Image

Approximating maximum properly colored forests via degree bounded independent sets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bai, Yuhang, Bérczi, Kristóf, Siemelink, Johanna K.
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

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

$\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions
by: Bérczi, Kristóf, 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)

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

Generalising the maximum independent set algorithm via Boolean networks
by: Gadouleau, Maximilien, et al.
Published: (2024)

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

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

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

Spanning tree congestion of proper interval graphs
by: Otachi, Yota
Published: (2026)

Faster single-source shortest paths with negative real weights via proper hop distance
by: Huang, Yufan, et al.
Published: (2024)

Approximation and parameterized algorithms for covering disjointness-compliable set families
by: Nutov, Zeev, et al.
Published: (2025)

A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
by: Czyżewska, Jadwiga, et al.
Published: (2025)

Packing $K_r$s in bounded degree graphs
by: McKay, Michael, et al.
Published: (2022)

Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
by: Mestel, David, et al.
Published: (2024)

Improved linearly ordered colorings of hypergraphs via SDP rounding
by: Louis, Anand, et al.
Published: (2024)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
by: Kowalik, Lukasz
Published: (2024)

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Parameterized Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2025)

Optimal (degree+1)-Coloring in Congested Clique
by: Coy, Sam, et al.
Published: (2023)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

Differentially private graph coloring
by: Xie, Michael, et al.
Published: (2026)

OptiRefine: Densest subgraphs and maximum cuts with $k$ refinements
by: Tu, Sijing, et al.
Published: (2025)

Improved bounds for coloring locally sparse hypergraphs
by: Iliopoulos, Fotis
Published: (2020)

Optimal FPT-Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2026)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
by: Friggstad, Zachary, et al.
Published: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

Probabilistic RNA Designability via Interpretable Ensemble Approximation and Dynamic Decomposition
by: Zhou, Tianshuo, et al.
Published: (2026)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
by: Lee, Dahoon, et al.
Published: (2025)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
by: Fang, Qiangpeng, et al.
Published: (2026)

Translating between the representations of an acyclic convex geometry of bounded degree
by: Defrain, Oscar, et al.
Published: (2025)