4 papers
The Power of Amortized Recourse for Online Graph Problems
Hsiang-Hsuan Liu, Jonathan Toole-Charignon
In this work, we study online graph problems with monotone-sum objectives. We propose a general two-fold greedy algorithm that references yardstick algorithms to achieve -compet…
P_3-Games on Chordal Bipartite Graphs
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu +3
Let G=(V,E) be a connected graph. A set U subseteq V is convex if G[U] is connected and all vertices of V\U have at most one neighbor in U. Let sigma(W) denote the unique smallest…
Convex Independence in Permutation Graphs
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu +1
A set C of vertices of a graph is P_3-convex if every vertex outside C has at most one neighbor in C. The convex hull σ(A) of a set A is the smallest P_3-convex set that contains A…
P_3-Games
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu +2
Without further ado, we present the P_3-game. The P_3-game is decidable for elementary classes of graphs such as paths and cycles. From an algorithmic point of view, the connected…