49 citations · 281 across the 22 of their papers we have counts for
20 papers · 1 filter
An Optimal Multiple-Class Encoding Scheme for a Graph of Bounded Hadwiger Number
Hsueh-I Lu
Since Jacobson [FOCS89] initiated the investigation of succinct graph encodings 35 years ago, there has been a long list of results on balancing the generality of the class, the sp…
A Simple 2-Approximation for Maximum-Leaf Spanning Tree
I-Cheng Liao, Hsueh-I Lu
For an -edge connected simple graph , finding a spanning tree of with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if is plan…
Improved Algorithms for Recognizing Perfect Graphs and Finding Shortest Odd and Even Holes
Yung-Chung Chiu, Kai-Yuan Lai, Hsueh-I Lu
Various classes of induced subgraphs are involved in the deepest results of graph theory and graph algorithms. A prominent example concerns the {\em perfection} of that the chr…
Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths
Yung-Chung Chiu, Hsueh-I Lu
For vertices and of an -vertex graph , a -trail of is an induced -path of that is not a shortest -path of . Berger, Seymour, and Spirkl [Discre…
Finding a Shortest Even Hole in Polynomial Time
Hou-Teng Cheong, Hsueh-I Lu
An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock [DM 1991 and 1992] proved that detecting an ev…
Three-in-a-Tree in Near Linear Time
Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup
The three-in-a-tree problem is to determine if a simple undirected graph contains an induced subgraph which is a tree connecting three given vertices. Based on a beautiful characte…