2 citations · 7 across the 12 of their papers we have counts for
13 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…
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu
We present a unified framework for minimizing average completion time for many seemingly disparate online scheduling problems, such as the traveling repairperson problems (TRP), di…
A Primal-Dual Online Deterministic Algorithm for Matching with Delays
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu +1
In the Min-cost Perfect Matching with Delays (MPMD) problem, 2 m requests arrive over time at points of a metric space. An online algorithm has to connect these requests in pairs,…
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…
On the Grundy number of Cameron graphs
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu +2
The Grundy number of a graph is the maximal number of colors attained by a first-fit coloring of the graph. The class of Cameron graphs is the Seidel switching class of cographs. I…
Non-preemptive Scheduling in a Smart Grid Model and its Implications on Machine Minimization
Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong
We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their reques…
Flood-it on AT-Free Graphs
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu +2
Solitaire {\sc Flood-it}, or {\sc Honey-Bee}, is a game played on a colored graph. The player resides in a source vertex. Originally his territory is the maximal connected, monochr…
Convexities in Some Special Graph Classes ---New Results in AT-free Graphs and Beyond
Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu +2
We study convexity properties of graphs. In this paper we present a linear-time algorithm for the geodetic number in tree-cographs. Settling a 10-year-old conjecture, we prove that…
Rainbow domination and related problems on some classes of perfect graphs
Wing-Kai Hon, Ton Kloks, Hsian-Hsuan Liu +1
Let and let be a graph. A function is a rainbow function if, for every vertex with , . The ra…
On Complexities of Minus Domination
Luérbio Faria, Wing-Kai Hon, Ton Kloks +3
A function f: V \rightarrow \{-1,0,1\} is a minus-domination function of a graph G=(V,E) if the values over the vertices in each closed neighborhood sum to a positive number. The w…
Results on independent sets in categorical products of graphs, the ultimate categorical independence ratio and the ultimate categorical independent domination ratio
Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu +2
We show that there are polynomial-time algorithms to compute maximum independent sets in the categorical products of two cographs and two splitgraphs. The ultimate categorical inde…
Independent set in categorical products of cographs and splitgraphs
W. Hon, T. Kloks, S. Liu +2
We show that there are polynomial-time algorithms to compute maximum independent sets in the categorical products of two cographs and two splitgraphs. We show that the ultimate cat…
On independence domination
Wing-Kai Hon, Ton Kloks, Hsiang Hsuan Liu +2
Let G be a graph. The independence-domination number is the maximum over all independent sets I in G of the minimal number of vertices needed to dominate I. In this paper we invest…