Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Above-Guarantee Algorithm for Properly Colored Trees
Yuhang Bai, Kristóf Bérczi
In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a spanning tree in which any two adjacent edges have distinct c…
cs.DS2025
Approximating maximum properly colored forests via degree bounded independent sets
Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink
In the Maximum-size Properly Colored Forest problem, we are given an edge-colored undirected graph and the goal is to find a properly colored forest with as many edges as possible.…
cs.DS2024
Approximating maximum-size properly colored forests
Yuhang Bai, Kristóf Bérczi, Gergely Csáji +1
In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree, i.e., a spanning tree in whic…