4 papers
Packing Compact Subgraphs with Applications to Districting
Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte +3
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e…
Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate
Ho-Lin Chen, Tsun Ming Cheung, Peng-Ting Lin +1
We study the space complexity of computing a sparse subgraph of a directed graph that certifies connectivity in the streaming and distributed models. Formally, for a directed graph…
Price of Anarchy of Multi-Stage Machine Scheduling Games
Ho-Lin Chen, Pin-Ju Huang
In this paper, we extend the discussion of the price of anarchy of machine scheduling games to a multi-stage machine setting. The multi-stage setting arises naturally in manufactur…
On the Simulation Power of Surface Chemical Reaction Networks
Yi-Xuan Lee, Ho-Lin Chen
The Chemical Reaction Network (CRN) is a well-studied model that describes the interaction of molecules in well-mixed solutions. In 2014, Qian and Winfree [22] proposed the abstrac…