Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Finding -colorings Using Feedback Edges
Jakub Balabán
A -coloring of a graph is a proper vertex coloring such that each color class contains a vertex that sees all other colors in its neighborhood. The -coloring problem, in whic…
cs.DS2025
Online Knapsack Problems with Estimates
Jakub Balabán, Matthias Gehnen, Henri Lotze +2
Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you…
cs.DS2025
Solving Partial Dominating Set and Related Problems Using Twin-Width
Jakub Balabán, Daniel Mock, Peter Rossmanith
Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are -hard on general graphs, they have been shown to be fixed-…