An Optimal Algorithm for the Maximum-Density Segment Problem (2003)
We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers $w_{\min}$ and $w_{\max}$ and a sequence $S$ of $n$ number pairs $(a_i,w_i)$ with...
On the Ramsey Numbers for Bipartite Multigraphs (2003)
Chen, Ming-Yang, Lu, Hsueh-I., Yen, Hsu-Chun
A coloring of a complete bipartite graph is shuffle-preserved if it is the case that assigning a color $c$ to edges $(u, v)$ and $(u', v')$ enforces the same color assignment for edges $(u, v')$ and...
Compact Floor-Planning via Orderly Spanning Trees (2003)
Chien-chih Liao, Hsueh-i Lu, Hsu-chun Yen
Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a oorplan for any n-node plane...
Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer (2002)
Lin, Ching-Chi, Lu, Hsueh-I, Sun, I-Fan
Let $G$ be an $n$-node planar graph. In a visibility representation of $G$, each node of $G$ is represented by a horizontal line segment such that the line segments representing any two adjacent...
Improved Compact Visibility Representation of (2002)
Let G be an n-node planar graph. In a visibility representation of G, each node of G is represented by a horizontal segment such that the segments representing any two adjacent nodes of G are...
Compact Floor-Planning via Orderly Spanning Trees (2002)
Liao, Chien-Chih, Lu, Hsueh-I, Yen, Hsu-Chun
Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a floor-plan for any n-node plane...
Detecting Race Conditions in Parallel Programs that Use Semaphores (2002)
Klein, Philip N., Lu, Hsueh-I, Netzer, Rob H. B.
We address the problem of detecting race conditions in programs that use semaphores for synchronization. Netzer and Miller showed that it is NP-complete to detect race conditions in programs that use...
Goldwasser, Michael H., Kao, Ming-Yang, Lu, Hsueh-I
We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (a_i,w_i) for i = 1,..,n and w_i>0, a segment A(i,j) is a consecutive subsequence of A...
Improved Compact Routing Tables for Planar (2002)
We address the problem of designing compact routing tables for an unlabeled connected n-node planar network G. For each node r of G, the designer is given a routing spanning tree Tr of G rooted at r,...
Some Applications of Orderly Spanning Trees in Graph Drawing (2002)
Chen, Ho-Lin, Liao, Chien-Chih, Lu, Hsueh-I., Yen, Hsu-Chun
Orderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this...
Floor-Planning via Orderly Spanning Trees (2002)
Liao, Chien-Chih, Lu, Hsueh-I., Yen, Hsu-Chun
Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple $O(n)$-time algorithm to construct a floor-plan for any $n$-node plane...
Some Applications of Orderly Spanning Trees in Graph Drawing (2002)
Chen, Ho-Lin, Liao, Chien-Chih, Lu, Hsueh-I., Yen, Hsu-Chun
Orderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this...
Floor-Planning via Orderly Spanning Trees (2002)
Liao, Chien-Chih, Lu, Hsueh-I., Yen, Hsu-Chun
Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple $O(n)$-time algorithm to construct a floor-plan for any $n$-node plane...
Some Applications of Orderly Spanning Trees in Graph Drawing (2002)
Chen, Ho-Lin, Liao, Chien-Chih, Lu, Hsueh-I., Yen, Hsu-Chun
Orderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this...
Floor-Planning via Orderly Spanning Trees (2002)
Liao, Chien-Chih, Lu, Hsueh-I., Yen, Hsu-Chun
Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple $O(n)$-time algorithm to construct a floor-plan for any $n$-node plane...
Linear-Time Compression of Bounded-Genus Graphs into (2001)
Introduction This extended abstract summarizes a new result for the graph compression problem, addressing how to compress a graph G into a binary string Z with the requirement that Z can be decoded...
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets (2001)
Chen, Yuyu, Kao, Ming-Yang, Lu, Hsueh-I
In a multiple-object auction, every bidder tries to win as many objects as possible with a bidding algorithm. This paper studies position-randomized auctions, which form a special class of...
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses (2001)
Chuang, Richie Chih-Nan, Garg, Ashim, He, Xin, Kao, Ming-Yang, Lu, Hsueh-I
Let G be a plane graph of n nodes, m edges, f faces, and no self-loop. G need not be connected or simple (i.e., free of multiple edges). We give three sets of coding schemes for G which all take...
Orderly Spanning Trees with Applications (2001)
Chiang, Yi-Ting, Lin, Ching-Chi, Lu, Hsueh-I
We introduce and study the {\em orderly spanning trees} of plane graphs. This algorithmic tool generalizes {\em canonical orderings}, which exist only for triconnected plane graphs. Although not...
Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings (2001)
He, Xin, Kao, Ming-Yang, Lu, Hsueh-I
Let G be an embedded planar undirected graph that has n vertices, m edges, and f faces but has no self-loop or multiple edge. If G is triangulated, we can encode it using {4/3}m-1 bits, improving on...
A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs (2001)
He, Xin, Kao, Ming-Yang, Lu, Hsueh-I
We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property pi is called a pi-graph. If pi satisfies certain...
On Maximum Symmetric Subgraphs (2001)
Chen, Ho-Lin, Lu, Hsueh-I., Yen, Hsu-Chun
Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally...
On Maximum Symmetric Subgraphs (2001)
Chen, Ho-Lin, Lu, Hsueh-I., Yen, Hsu-Chun
Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally...
On Maximum Symmetric Subgraphs (2001)
Chen, Ho-Lin, Lu, Hsueh-I., Yen, Hsu-Chun
Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally...
On Maximum Symmetric Subgraphs (2000)
Ho-lin Chen, Hsueh-i Lu, Hsu-chun Yen
Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally...
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets (2000)
Yuyu Chen, Ming-yang Kao, Hsueh-i Lu
In a multiple-object auction, every bidder tries to win as many objects as possible with a bidding algorithm. This paper studies position-randomized auctions, which form a special class of...
Approximating Maximum Leaf Spanning Trees in Almost Linear Time (2000)
Given an undirected graph, finding a spanning tree of the graph with maximum number of leaves is MAX SNP-complete. In this paper we give a new greedy 3-approximation algorithm for maximum-leaf...
The Power of Local Optimization: Approximation Algorithms for Maximum-Leaf Spanning Tree (2000)
Given an undirected graph G, finding a spanning tree of G with the maximum number of leaves is NP-complete [5]. We use the simple technique of local optimization to provide the first approximation...
The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, first finds the optimal solution of a semidefinite program and then derives a graph cut from that solution....
Detecting Race Conditions in Parallel Programs that Use One Semaphore (1999)
. We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that...
Race-Condition Detection in Parallel Computation with Semaphores (1999)
We address a problem arising in debugging parallel programs, detecting race conditions in programs using semaphores for synchronization. It is NPcomplete to detect race conditions in programs that...
Race-Condition Detection in Parallel Computation with Semaphores (1999)
We address a problem arising in debugging parallel programs, detecting race conditions in programs using semaphores for synchronization. It is NPcomplete to detect race conditions in programs that...
Space-efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs (1999)
The essential part of the best known approximation algorithm for graph MAXCUT is approximately solving MAXCUT's semidefinite relaxation. For a graph with n nodes and m edges, previous work on solving...
The Power of Local Optimization: Approximation Algorithms for Maximum-Leaf Spanning Tree (1998)
Given an undirected graph G, finding a spanning tree of G with the maximum number of leaves is NP-complete [5]. We use the simple technique of local optimization to provide the first approximation...
Efficient approximation algorithms for some semidefinite programs /--by Hsueh-I Lu. (1997)
Available in film copy from University Microfilms International.
Efficient Approximation Algorithms for Some Semidefinite Programs (1996)
Hsueh-i Lu, Philip N. Klein, Franco P. Preparata, Pascal Van Hentenryck
ization problems. Nonlinear programming did not receive as much attention in this respect until the recent work by Goemans and Williamson [62]. They use semidefinite programs, which are nonlinear...
Detecting Race Conditions in Parallel Programs that Use one Semaphore (1996)
. We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that...
Philip N. Klein, Philip Klein, Hsueh-i Lu
The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, first finds the optimal solution a semidefinite program and then derives a graph cut from that solution....
Detecting Race Conditions in Parallel Programs that Use One Semaphore (1996)
. We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that...
Philip N. Klein, Philip Klein, Hsueh-i Lu
The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, first finds the optimal solution a semidefinite program and then derives a graph cut from that solution....
Race-Condition Detection in Parallel Computation with Semaphores (1996)
We address a problem arising in debugging parallel programs, detecting race conditions in programs using semaphores for synchronization. It is NPcomplete to detect race conditions in programs that...
The Power of Local Optimization: Approximation Algorithms for Maximum-leaf Spanning Tree (1996)
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is NP-complete. We use the simple technique of local optimization to provide the first approximation algorithms...
A Near-linear-time Approximation Algorithm for Maximum-leaf Spanning Tree (1996)
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete [11] but also MAX SNP-complete [10]. The approximation ratio of the previously best...
Race-Condition Detection in Parallel Computation with Semaphores (1996)
We address a problem arising in debugging parallel programs, detecting race conditions in programs using semaphores for synchronization. It is NPcomplete to detect race conditions in programs that...
A Near-linear-time Approximation Algorithm for Maximum-leaf Spanning Tree (1996)
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete [11] but also MAX SNP-complete [10]. The approximation ratio of the previously best...
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is NP-complete. We use the simple technique of local optimization to provide the first approximation algorithms...
A Near-linear-time Approximation Algorithm for Maximum-leaf Spanning Tree (1970)
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete [11] but also MAX SNP-complete [10]. The approximation ratio of the previously best...
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses (1970)
. Let G be a plane graph of n nodes, m edges, f faces, and no self-loop. G need not be connected or simple (i.e., free of multiple edges). We give three sets of coding schemes for G which all take...