280 An Optimal Algorithm for Online Square Detection (2008)
Gen-huey Chen, Jin-ju Hong, Hsueh-i Lu
Abstract. A square is the concatenation of two identical non-empty strings. Let S be the input string which is given character by character. Let m be the (unknown) smallest integer such that the m-th...
Planar Graph, Via Schnyder’s Realizer, Ching-chi Lin, Hsueh-i Lu, I-fan Sun
Abstract. Let G be an n-node planar graph. In a visibility representation of G,eachnodeofG is represented by a horizontal line segment such that the line segments representing any two adjacent nodes...
Balanced Parentheses Strike Back (2008)
An ordinal tree is an arbitrary rooted tree where the children of each node are ordered. Succinct representations for ordinal trees with efficient query support have been extensively studied. The...
URL: www.cs.luc.edu/~mhg (2007)
Michael H. Goldwasser, Ming-yang Kao, Hsueh-i Lu
URL: www.cs.northwestern.edu/~kao
Compact Floor-Planning via Orderly Spanning Trees (2007)
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...
Orderly Spanning Trees with Applications (2005)
Yi-ting Chiang, Ching-chi Lin, Hsueh-i Lu
Abstract. We introduce and study orderly spanning trees of plane graphs. This algorithmic tool generalizes canonical orderings, which exist only for triconnected plane graphs. Although not every...
Power-saving scheduling for weakly dynamic voltage scaling devices (2005)
Jian-jia Chen, Tei-wei Kuo, Hsueh-i Lu
Abstract. We study the problem of non-preemptive scheduling to minimize energy consumption for devices that allow dynamic voltage scaling. Specifically, consider a device that can process jobs in a...
An Optimal Algorithm for the Maximum-Density Segment Problem (2004)
Abstract. We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers wmin and wmax and a sequence S of n number pairs (ai,wi) with wi> 0....
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...
Detecting Race Conditions in Parallel Programs that Use Semaphores (2003)
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...
Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer (2003)
Ching-Chi Lin, Hsueh-I Lu, I-Fan Sun
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...
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...
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...
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...
Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees (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,...
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...
Orderly spanning trees with applications to graph encoding and graph drawing (2001)
Yi-ting Chiang, Ching-chi Lin, Hsueh-i Lu
The canonical ordering for triconnected planar graphs is a powerful method for designing graph algorithms. This paper introduces the orderly pair of connected planar graphs, which extends the concept...
On Maximum Symmetric Subgraphs (2001)
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...
Linear-time succinct encodings of planar graphs via canonical orderings (1999)
Xin He, Ming-yang Kao, Hsueh-i Lu
Abstract. 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 m − 1 bits,...
A Fast General Methodology For Information-Theoretically Optimal Encodings Of Graphs (1999)
Xin He, Ming-yang Kao, Hsueh-I Lu
. We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property is called a -graph. If satisfies certain properties,...
Approximating Maximum Leaf Spanning Trees in Almost Linear Time (1998)
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...
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses (1998)
Ashim Garg, Xin He, Ming-Yang Kao, Hsueh-i Lu
. We consider the problem of coding planar graphs by binary strings. Depending on whether O(1)-time queries for adjacency and degree are supported, we present three sets of coding schemes which all...
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses (1998)
ASHIM GARG, XIN HE, MING-YANG KAO, Hsueh-i Lu
. 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...
Efficient approximation algorithms for some semidefinite programs /--by Hsueh-I Lu. (1997)
Available in film copy from University Microfilms International.
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...
Race-Condition Detection in Parallel Computation with Semaphores (1996)
Philip N. Klein, Philip N. Klein, Hsueh-i Lu, Hsueh-i Lu
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...
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...
Efficient Approximation Algorithms for Some Semidefinite Programs (1996)
Hsueh-i Lu, 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...
Philip N. Klein, Philip Klein, Hsueh-i Lu, 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....
Space-efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs (1996)
. 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...
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...
Space-efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs (1996)
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...
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 (1993)
Hsueh-i Lu, Hsueh-i Lu, Philip N. Klein, Philip N. Klein
. 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...
The Power of Local Optimization: Approximation Algorithms for Maximum-Leaf Spanning Tree (1992)
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...