58 citations · 239 across the 47 of their papers we have counts for
6 papers · 1 filter
Structural Parameterizations for Eternal Vertex Cover
Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani +1
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph . To begin with, the defender places guards on vertices of . The attacker, on the…
Bounding Width on Graph Classes of Constant Diameter
Konrad K. Dabrowski, Tala Eagling-Vose, Noleen Köhler +2
We determine if the width of a graph class changes from unbounded to bounded if we consider only those graphs from whose diameter is bounded. As parameters we…
Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises
Cornelius Brand, Martin Koutecký, Alexandra Lassota +1
An influential 1990 paper of Hochbaum and Shanthikumar made it common wisdom that "convex separable optimization is not much harder than linear optimization" [JACM 1990]. We exhibi…
Solving Integer Linear Programs with a Small Number of Global Variables and Constraints
Pavel Dvořák, Eduard Eiben, Robert Ganian +2
Integer Linear Programming (ILP) has a broad range of applications in various areas of artificial intelligence. Yet in spite of recent advances, we still lack a thorough understand…
Tree-depth and Vertex-minors
Petr Hliněný, O-joung Kwon, Jan Obdržálek +1
In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already befor…
Digraph Decompositions and Monotonicity in Digraph Searching
Stephan Kreutzer, Sebastian Ordyniak
We consider monotonicity problems for graph searching games. Variants of these games - defined by the type of moves allowed for the players - have been found to be closely connecte…