Source author record

Hai-Lun Tu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

O(f) Bi-Approximation for Capacitated Covering with Hard Capacities

We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph $G=(V,E)$ with a maximum edge size $f$ . Each edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset such that the demands of the edges can be covered by the capacities of the vertices and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an $O(f)$ bi-approximation for VC-HC that gives a trade-off on the number of augmented multiplicity and the cost of the resulting cover. In particular, we show that, by augmenting the available multiplicity by a factor of $k \ge 2$ , a~cover with a cost ratio of $\Big(1+\frac{1}{k-1}\Big)(f-1)$ to the optimal cover for the original instance can be obtained. This improves over a previous result, which has a cost ratio of $f^2$ via augmenting the available multiplicity by a factor of $f$ .

preprint2014arXiv

Linear-Time Algorithms for the Paired-Domination Problem in Interval Graphs and Circular-Arc Graphs

In a graph $G$ , a vertex subset $S\subseteq V(G)$ is said to be a dominating set of $G$ if every vertex not in $S$ is adjacent to a vertex in $S$ . A dominating set $S$ of a graph $G$ is called a paired-dominating set if the induced subgraph $G[S]$ contains a perfect matching. The paired-domination problem involves finding a smallest paired-dominating set of $G$ . Given an intersection model of an interval graph $G$ with sorted endpoints, Cheng et al. designed an $O(m+n)$ -time algorithm for interval graphs and an $O(m(m+n))$ -time algorithm for circular-arc graphs. In this paper, to solve the paired-domination problem in interval graphs, we propose an $O(n)$ -time algorithm that searches for a minimum paired-dominating set of $G$ incrementally in a greedy manner. Then, we extend the results to design an algorithm for circular-arc graphs that also runs in $O(n)$ time.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.