Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. (English) Zbl 1315.05130
Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 79-88 (2014).
MSC:
| 05C83 | Graph minors |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C57 | Games on graphs (graph-theoretic aspects) |
Software:
SuLQReferences:
| [1] | Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strong-diameter decompositions of minor free graphs. Theory Comput. Syst., 47(4):837-855, 2010. 10.1007/s00224-010-9283-6 · Zbl 1215.68166 |
| [2] | Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs. J. Amer. Math. Soc., 3(4):801-808, 1990. · Zbl 0747.05051 |
| [3] | Thomas Andreae. On a pursuit game played on graphs for which a minor is excluded. J. Combin. Theory Ser. B, 41(1):37-47, 1986. 10.1016/0095-8956(86)90026-2 · Zbl 0641.90110 |
| [4] | Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Éva Tardos. Approximate classification via earthmover metrics. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1079-1087, New York, 2004. ACM. · Zbl 1318.68193 |
| [5] | Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804-823, October 1985. 10.1145/4221.4227 · Zbl 0628.68045 |
| [6] | Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, pages 184–, Washington, DC, USA, 1996. IEEE Computer Society. |
| [7] | Punyashloka Biswal, James R. Lee, and Satish Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via ows. J. ACM, 57(3), 2010. 10.1145/1706591.1706593 · Zbl 1327.05199 |
| [8] | Glencora Borradaile, James R. Lee, and Anastasios Sidiropoulos. Randomly removing g handles at once. Comput. Geom., 43(8):655-662, 2010. 10.1016/j.comgeo.2010.04.007 · Zbl 1207.05038 |
| [9] | Costas Busch, Ryan LaFortune, and Srikanta Tirthapura. Improved sparse covers for graphs excluding a fixed minor. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, PODC ’07, pages 61-70, New York, NY, USA, 2007. ACM. 10.1145/1281100.1281112 · Zbl 1283.68080 |
| [10] | Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. SIAM J. Comput., 34(2):358-372, 2004/05. 10.1137/S0097539701395978 · Zbl 1087.68128 |
| [11] | Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2000. · Zbl 0945.05002 |
| [12] | Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485-497, 2004. 10.1016/j.jcss.2004.04.011 · Zbl 1071.68082 |
| [13] | Jittat Fakcharoenphol and Kunal Talwar. An improved decomposition theorem for graphs excluding a fixed minor. RANDOM-APPROX, pages 36-46, 2003. · Zbl 1279.05053 |
| [14] | Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629-657, 2008. 10.1137/05064299X · Zbl 1172.68063 |
| [15] | Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In FOCS, pages 534-543, 2003. |
| [16] | Piotr Indyk and Anastasios Sidiropoulos. Probabilistic embeddings of bounded genus graphs into planar graphs. In Symposium on Computational Geometry, pages 204-209, 2007. 10.1145/1247069.1247107 · Zbl 1207.05040 |
| [17] | Jonathan A. Kelner, James R. Lee, Gregory N. Price, and Shang-Hua Teng. Higher eigenvalues of graphs. In FOCS, pages 735-744, 2009. 10.1109/FOCS.2009.69 · Zbl 1292.05172 |
| [18] | Philip N. Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In STOC, pages 682-690, 1993. 10.1145/167088.167261 · Zbl 1310.90017 |
| [19] | James R. Lee. Open question recap, February 2013. http://tcsmath.wordpress.com/2013/02/25/openquestion-recap/. |
| [20] | James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multi-way spectral partitioning and higher-order cheeger inequalities. In STOC, pages 1117-1130, 2012. 10.1145/2213977.2214078 · Zbl 1286.05091 |
| [21] | James R. Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59-95, 2005. · Zbl 1074.46004 |
| [22] | James R. Lee and Anastasios Sidiropoulos. Genus and the geometry of the cut graph. In SODA, pages 193-201, 2010. · Zbl 1288.05062 |
| [23] | Nathan Linial and Michael Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. (Preliminary version in 2nd SODA, 1991). · Zbl 0790.05067 |
| [24] | Jiří Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. · Zbl 0999.52006 |
| [25] | Serge Plotkin, Satish Rao, and Warren D. Smith. Shallow excluded minors and improved graph decompositions. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), pages 462-470, New York, 1994. ACM. · Zbl 0867.05069 |
| [26] | Yuri Rabinovich. On average distortion of embedding metrics into the line and into ℓ1. In Proceedings of the thirty-fifth ACM symposium on Theory of computing, pages 456-462. ACM Press, 2003. 10.1145/780542.780609 · Zbl 1192.90237 |
| [27] | Satish B. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In SOCG, pages 300-306, 1999. 10.1145/304893.304983 |
| [28] | Neil Robertson and Paul D. Seymour. Graph minors. XVI. excluding a non-planar graph. Journal of Combinatorial Theory, Series B, 89(1):43-76, 2003. 10.1016/S0095-8956(03)00042-X · Zbl 1023.05040 |
| [29] | Anastasios Sidiropoulos. Optimal stochastic planarization. In FOCS, pages 163-170, 2010. 10.1109/FOCS.2010.23 |
| [30] | Christian Wulff-Nilsen. Separator theorems for minor-free and shallow minor-free graphs with applications. In FOCS, pages 37-46, 2011. 10.1109/FOCS.2011.15 · Zbl 1292.68129 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
