Hsueh-I Lu

STOC Conference 2020 Conference Paper

Three-in-a-tree in near linear time

• Kai-Yuan Lai 0001
• Hsueh-I Lu
• Mikkel Thorup

SODA Conference 2012 Conference Paper

A faster algorithm to recognize even-hole-free graphs

• Hsien-Chih Chang
• Hsueh-I Lu

We study the problem of determining whether an n -node m -edge graph has an even hole, i. e. , an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomial-time algorithm for the problem, which runs in O ( n 40 ) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O ( n 31 ). The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O ( n 19 ) time. In this paper, we solve the problem in time O ( n 11 ).

SODA Conference 2002 Conference Paper

Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits

• Hsueh-I Lu

SODA Conference 2001 Conference Paper

Orderly spanning trees with applications to graph encoding and graph drawing

• Yi-Ting Chiang
• Ching-Chi Lin
• Hsueh-I Lu

STOC Conference 1996 Conference Paper

Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING

• Philip N. Klein
• Hsueh-I Lu