24 citations · 67 across the 14 of their papers we have counts for
10 papers · 1 filter
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCLMST23], is a new type of graph partition into low-diameter clusters. R…
Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
Recently the authors [CCLMST23] introduced the notion of shortcut partition of planar graphs and obtained several results from the partition, including a tree cover with tre…
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of…
Near-Linear -Emulators for Planar Graphs
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph (with edge weights) and a subset of terminal vertices, t…
Deterministic, Near-Linear -Approximation Algorithm for Geometric Bipartite Matching
Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra +1
Given point sets and in where and have equal size for some constant dimension and a parameter , we present the first determini…
Clustering under Perturbation Stability in Near-Linear Time
Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala +2
We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is -stable if the underlying opti…
Efficient Algorithms for Geometric Partial Matching
Pankaj K. Agarwal, Hsien-Chih Chang, Allen Xiao
Let and be two point sets in the plane of sizes and respectively (assume ), and let be a parameter. A matching between and is a family of pair…
Near-Optimal Distance Emulator for Planar Graphs
Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes +1
Given a graph and a set of terminals , a \emph{distance emulator} of is another graph (not necessarily a subgraph of ) containing , such that all the pairwise…
A Faster Algorithm to Recognize Even-Hole-Free Graphs
Hsien-Chih Chang, Hsueh-I Lu
We study the problem of determining whether an -node graph has an even hole, i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoo…
Computing the Girth of a Planar Graph in Linear Time
Hsien-Chih Chang, Hsueh-I Lu
The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an n-node unweighted undirected planar graph. The fir…