STOC Conference 2008 Conference Paper
An o(log 2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem
- Jittat Fakcharoenphol
- Bundit Laekhanukit
Author name cluster
Jittat Fakcharoenphol
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
7 papers
1 author row
Possible papers
7SODA Conference 2004 Conference Paper
A deterministic near-linear time algorithm for finding minimum cuts in planar graphs
- Parinya Chalermsook
- Jittat Fakcharoenphol
- Danupon Nanongkai
SODA Conference 2004 Conference Paper
Approximate classification via earthmover metrics
- Aaron Archer
- Jittat Fakcharoenphol
- Chris Harrelson
- Robert Krauthgamer
- Kunal Talwar
- Éva Tardos
STOC Conference 2003 Conference Paper
A tight bound on approximating arbitrary metrics by tree metrics
- Jittat Fakcharoenphol
- Satish Rao
- Kunal Talwar
SODA Conference 2003 Conference Paper
An improved approximation algorithm for the 0-extension problem
- Jittat Fakcharoenphol
- Chris Harrelson
- Satish Rao
- Kunal Talwar
SODA Conference 2003 Conference Paper
The k-traveling repairman problem
- Jittat Fakcharoenphol
- Chris Harrelson
- Satish Rao
FOCS Conference 2001 Conference Paper
Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time
- Jittat Fakcharoenphol
- Satish Rao
The authors present an O(n log/sup 3/ n) time algorithm for finding shortest paths in a planar graph with real weights. This can be compared to the best previous strongly polynomial time algorithm developed by R. Lipton et al. , (1978 )which ran in O(n/sup 3/2/) time, and the best polynomial algorithm developed by M. Henzinger et al. (1994) which ran in O/spl tilde/(n/sup 4/3/) time. We also present significantly improved algorithms for query and dynamic versions of the shortest path problems.