# | Document title | Authors | Year | Source | Cited by |
1 | From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more | Chalermsook P., Cygan M., Kortsarz G., Laekhanukit B., Laekhanukit B., Manurangsi P., Nanongkai D., Trevisan L. | 2020 | SIAM Journal on Computing 49(4),pp. 772-810 | 6 |
2 | Surviving in directed graphs: A quasi-polynomial-time polylogarithmic approximation for two-connected directed steiner tree | Grandoni F., Laekhanukit B. | 2017 | Proceedings of the Annual ACM Symposium on Theory of Computing Part F128415,pp. 420-428 | 5 |
3 | A rounding by sampling approach to the minimum size k-arc connected subgraph problem | Laekhanukit B., Oveis Gharan S., Singh M., Singh M. | 2012 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7391 LNCS(PART 1),pp. 606-616 | 8 |
4 | Pre-reduction graph products: Hardnesses of properly learning DFAs and approximating EDP on DAGs | Chalermsook P., Laekhanukit B., Laekhanukit B., Nanongkai D. | 2014 | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS ,pp. 444-453 | 4 |
5 | On the parameterized complexity of approximating dominating set | Karthik C., Laekhanukit B., Manurangsi P. | 2019 | Journal of the ACM 66(5) | 19 |
6 | Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity | Liao C., Chen Q., Laekhanukit B., Zhang Y. | 2022 | Leibniz International Proceedings in Informatics, LIPIcs 229 | 0 |
7 | An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem | Laekhanukit B. | 2015 | Algorithmica 72(3),pp. 714-733 | 7 |
8 | Beyond metric embedding: Approximating group steiner trees on bounded treewidth graphs | Chalermsook P., Das S., Laekhanukit B., Vaz D., Vaz D. | 2017 | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 0,pp. 737-751 | 6 |
9 | On the complexity of closest pair via polar-pair of point-sets | David R., Karthik C., Laekhanukit B., Laekhanukit B. | 2018 | Leibniz International Proceedings in Informatics, LIPIcs 99,pp. 281-2815 | 2 |
10 | Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses | Chalermsook P., Laekhanukit B., Nanongkai D. | 2013 | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS ,pp. 370-379 | 43 |
11 | Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting | Yingchareonthawornchai S., Roy P.C., Laekhanukit B., Torng E., Deb K. | 2020 | GECCO 2020 Companion - Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion ,pp. 185-186 | 1 |
12 | Approximating rooted Steiner networks | Cheriyan J., Laekhanukit B., Naves G., Naves G., Vetta A. | 2014 | ACM Transactions on Algorithms 11(2) | 8 |
13 | Coloring graph powers: Graph product bounds and hardness of approximation | Chalermsook P., Laekhanukit B., Nanongkai D. | 2014 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8392 LNCS,pp. 409-420 | 5 |
14 | Faster algorithms for semi-matching problems | Fakcharoenphol J., Laekhanukit B., Nanongkai D. | 2014 | ACM Transactions on Algorithms 10(3) | 14 |
15 | On approximating degree-bounded network design problems | Guo X., Kortsarz G., Laekhanukit B., Li S., Vaz D., Xian J. | 2020 | Leibniz International Proceedings in Informatics, LIPIcs 176 | 0 |
16 | O(log2 k/ log log k)-approximation algorithm for directed steiner tree: A tight quasi-polynomial-time algorithm | Grandoni F., Laekhanukit B., Li S. | 2019 | Proceedings of the Annual ACM Symposium on Theory of Computing ,pp. 253-264 | 18 |
17 | Routing regardless of network stability | Laekhanukit B., Vetta A., Wilfong G. | 2012 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7501 LNCS,pp. 719-730 | 0 |
18 | An O(log2 k)-Approximation algorithm for the k-Vertex connected spanning subgraph problem | Fakcharoenphol J., Laekhanukit B. | 2008 | Proceedings of the Annual ACM Symposium on Theory of Computing ,pp. 153-158 | 25 |
19 | Polynomial Integrality Gap of Flow LP for Directed Steiner Tree | Li S., Laekhanukit B. | 2022 | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 2022-January,pp. 3230-3236 | 0 |
20 | Polylogarithmic approximation algorithm for k-connected directed steiner tree on quasi-bipartite graphs | Chan C.H., Laekhanukit B., Wei H.T., Zhang Y. | 2020 | Leibniz International Proceedings in Informatics, LIPIcs 176 | 2 |
21 | Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more | Chalermsook P., Laekhanukit B., Nanongkai D. | 2013 | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms ,pp. 1557-1576 | 36 |
22 | On Approximating Degree-Bounded Network Design Problems | Guo X., Kortsarz G., Laekhanukit B., Li S., Vaz D., Xian J. | 2022 | Algorithmica
| 0 |
23 | On survivable set connectivity | Chalermsook P., Grandoni F., Laekhanukit B. | 2015 | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 2015-January(January),pp. 25-36 | 6 |
24 | Faster algorithms for semi-matching problems | Fakcharoenphol J., Laekhanukit B., Nanongkai D. | 2010 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6198 LNCS(PART 1),pp. 176-187 | 11 |
25 | Parameters of two-prover-one-round game and the hardness of connectivity problems | Laekhanukit B. | 2014 | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms ,pp. 1626-1643 | 21 |
26 | On the Approximability of the Traveling Salesman Problem with Line Neighborhoods | Antoniadis A., Kisfaludi-Bak S., Laekhanukit B., Vaz D. | 2022 | Leibniz International Proceedings in Informatics, LIPIcs 227 | 0 |
27 | On the parameterized complexity of approximating dominating set | Karthik C., Laekhanukit B., Laekhanukit B., Manurangsi P. | 2018 | Proceedings of the Annual ACM Symposium on Theory of Computing ,pp. 815-826 | 18 |
28 | Routing regardless of network stability | Laekhanukit B., Vetta A., Wilfong G. | 2014 | Algorithmica 70(3),pp. 561-593 | 0 |
29 | From Gap-ETH to FPT-inapproximability: Clique, dominating set, and more | Chalermsook P., Cygan M., Kortsarz G., Laekhanukit B., Laekhanukit B., Manurangsi P., Nanongkai D., Trevisan L. | 2017 | Annual Symposium on Foundations of Computer Science - Proceedings 2017-October,pp. 743-754 | 51 |
30 | Approximating Spanners and Directed Steiner Forest | Chlamtáč E., Dinitz M., Kortsarz G., Laekhanukit B. | 2020 | ACM Transactions on Algorithms 16(3) | 1 |
31 | Approximating rooted steiner networks | Cheriyan J., Laekhanukit B., Naves G., Vetta A. | 2012 | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms ,pp. 1499-1511 | 6 |
32 | Improved hardness of approximation for Stackelberg shortest-path pricing | Briest P., Chalermsook P., Khanna S., Laekhanukit B., Nanongkai D. | 2010 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6484 LNCS,pp. 444-454 | 13 |
33 | New Tools and Connections for Exponential-Time Approximation | Bansal N., Chalermsook P., Laekhanukit B., Nanongkai D., Nederlof J. | 2019 | Algorithmica 81(10),pp. 3993-4009 | 7 |
34 | Vertex sparsification for edge connectivity | Chalermsook P., Das S., Kook Y., Laekhanukit B., Liu Y.P., Peng R., Sellke M., Vaz D. | 2021 | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms ,pp. 1206-1225 | 5 |
35 | Approximation algorithms for minimum-cost k-(S, T ) connected digraphs | Cheriyan J., Laekhanukit B. | 2013 | SIAM Journal on Discrete Mathematics 27(3),pp. 1450-1481 | 4 |
36 | A bad example for the iterative rounding method for mincost k-connected spanning subgraphs | Aazami A., Cheriyan J., Laekhanukit B. | 2013 | Discrete Optimization 10(1),pp. 25-41 | 7 |
37 | Approximating directed Steiner problems via tree embedding | Laekhanukit B. | 2016 | Leibniz International Proceedings in Informatics, LIPIcs 55 | 5 |
38 | Survivable network design for group connectivity in low-treewidth graphs | Chalermsook P., Das S., Even G., Laekhanukit B., Laekhanukit B., Vaz D. | 2018 | Leibniz International Proceedings in Informatics, LIPIcs 116 | 3 |
39 | An improved approximation algorithm for minimum-cost subset k-connectivity | Laekhanukit B. | 2011 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6755 LNCS(PART 1),pp. 13-24 | 8 |
40 | An O(log 2 k)-Approximation algorithm for the k-vertex connected spanning Subgraph problem | Fakcharoenphol J., Laekhanukit B. | 2012 | SIAM Journal on Computing 41(5),pp. 1095-1109 | 15 |
41 | Non-redistributive second welfare theorems | Laekhanukit B., Naves G., Vetta A. | 2012 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7695 LNCS,pp. 227-243 | 0 |
42 | On the complexity of closest pair via polar-pair of point-sets | David R., Karthik C., Laekhanukit B. | 2019 | SIAM Journal on Discrete Mathematics 33(1),pp. 509-527 | 10 |