49 citations · 171 across the 6 of their papers we have counts for
8 papers · 1 filter
An Optimal Algorithm for the Maximum-Density Segment Problem
Kai-min Chung, Hsueh-I Lu
We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers and and a sequence of number pairs…
Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer
Ching-Chi Lin, Hsueh-I Lu, I-Fan Sun
Let be an -node planar graph. In a visibility representation of , each node of is represented by a horizontal line segment such that the line segments representing an…
Compact Floor-Planning via Orderly Spanning Trees
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 floor-plan for an…
Detecting Race Conditions in Parallel Programs that Use Semaphores
Philip N. Klein, Hsueh-I Lu, Rob H. B. Netzer
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 i…
Linear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications
Michael H. Goldwasser, Ming-Yang Kao, Hsueh-I Lu
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 consecuti…
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses
Richie Chih-Nan Chuang, Ashim Garg, Xin He +2
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…