7 papers
From b-Coloring to -Coloring: Large Girth and Parameterized Complexity
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…
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…
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-…
Twin-Width Meets Feedback Edges and Vertex Integrity
Jakub Balabán, Robert Ganian, Mathis Rocton
The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towar…
Computing Twin-Width Parameterized by the Feedback Edge Number
Jakub Balabán, Robert Ganian, Mathis Rocton
The problem of whether and how one can compute the twin-width of a graph -- along with an accompanying contraction sequence -- lies at the forefront of the area of algorithmic mode…