5 papers
From b-Coloring to -Coloring: Large Girth and Parameterized Complexity
Jakub Balabán, Jakub Balabán, Oliver Bukor
A b-coloring is a proper vertex coloring such that every color class contains a vertex, a so-called b-vertex, which sees all colors in its closed neighborhood. This type of colorin…
Measuring Depth of Matroids
Jakub Balabán, Petr HlinÄný, Jan Jedelský +1
Motivated by recently discovered connections between matroid depth measures and block-structured integer programming [ICALP 2020, 2022], we undertake a systematic study of recursiv…
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…
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-…
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…