Articles under category:
Graphs
Graphs
Vol 18, Article 18 (pp 1-19)
Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks by Chandra Chekuri and Tanmay Inamdar |
Vol 18, Article 7 (pp 1-24)
[APRX-RND19 Spec Issue]
Fast and Deterministic Approximations for $k$-Cut by Kent Quanrud |
Vol 17, Article 6 (pp 1-57)
Almost Polynomial Hardness of Node-Disjoint Paths in Grids by Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat |
Vol 16, Article 1 (pp 1-23)
Distributed Corruption Detection in Networks by Noga Alon, Elchanan Mossel, and Robin Pemantle |
Vol 13, Article 8 (pp 1-22)
[APRX-RND15 Spec Issue]
The Minimum Bisection in the Planted Bisection Model by Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch |
Vol 13, Article 5 (pp 1-47)
[APRX-RND13 Spec Issue]
A Pseudo-Approximation for the Genus of Hamiltonian Graphs by Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos |
Vol 12, Article 19 (pp 1-33)
Locally Checkable Proofs in Distributed Computing by Mika Göös and Jukka Suomela |
Vol 11, Article 13 (pp 339-355)
Computing the Partition Function for Cliques in a Graph by Alexander Barvinok |
Vol 9, Article 24 (pp 759-781)
[APRX-RND12 Spec Issue]
Hardness of Vertex Deletion and Project Scheduling by Ola Svensson |
Vol 9, Article 11 (pp 413-435)
Improved Inapproximability Results for Maximum $k$-Colorable Subgraph by Venkatesan Guruswami and Ali Kemal Sinop |
Vol 9, Article 6 (pp 273-282)
[NOTE]
The Complexity of the Fermionant and Immanants of Constant Width by Stephan Mertens and Cristopher Moore |
Vol 8, Article 25 (pp 567-595)
[Motwani Special Issue]
Online Graph Edge-Coloring in the Random-Order Arrival Model by Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani |
Vol 8, Article 18 (pp 401-413)
[Motwani Special Issue]
An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design by Julia Chuzhoy and Sanjeev Khanna |
Vol 7, Article 3 (pp 27-43)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs by Per Austrin, Subhash Khot, and Muli Safra |
Vol 6, Article 12 (pp 291-308)
[RESEARCH SURVEY]
Monotone Expanders: Constructions and Applications by Zeev Dvir and Avi Wigderson |
Vol 5, Article 9 (pp 173-189)
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time by Virginia Vassilevska, R. Ryan Williams, and Raphael Yuster |
Vol 4, Article 9 (pp 191-193)
[COMMENT]
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem by Viswanath Nagarajan |
Vol 4, Article 1 (pp 1-20)
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall |
Vol 3, Article 10 (pp 197-209)
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem by Chandra Chekuri and Martin Pál |
■
|
Vol 2, Article 7 (pp 137-146)
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd |
Vol 2, Article 5 (pp 91-120)
Iterative Construction of Cayley Expander Graphs by Eyal Rozenman, Aner Shalev, and Avi Wigderson |