Fox-Epstein, Eli; Klein, Philip N.; Schild, Aaron Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems. (English) Zbl 1431.68093 Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1069-1088 (2019). MSC: 68R10 05C10 68W25 PDFBibTeX XMLCite \textit{E. Fox-Epstein} et al., in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6--9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1069--1088 (2019; Zbl 1431.68093) Full Text: DOI
Becker, Amariah; Klein, Philip N.; Saulpic, David A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs. (English) Zbl 1442.90192 Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 12, 15 p. (2017). MSC: 90C35 05C10 68W25 90B20 PDFBibTeX XMLCite \textit{A. Becker} et al., LIPIcs -- Leibniz Int. Proc. Inform. 87, Article 12, 15 p. (2017; Zbl 1442.90192) Full Text: DOI
Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; Wulff-Nilsen, Christian Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. (English) Zbl 1368.05032 SIAM J. Comput. 46, No. 4, 1280-1303 (2017). MSC: 05C10 05C21 05C20 05C85 PDFBibTeX XMLCite \textit{G. Borradaile} et al., SIAM J. Comput. 46, No. 4, 1280--1303 (2017; Zbl 1368.05032) Full Text: DOI
Cohen-Addad, Vincent; Colin de Verdière, Éric; Klein, Philip N.; Mathieu, Claire; Meierfrankenfeld, David Approximating connectivity domination in weighted bounded-genus graphs. (English) Zbl 1376.68171 Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 584-597 (2016). MSC: 68W25 05C10 05C22 05C69 05C70 05C85 68Q25 PDFBibTeX XMLCite \textit{V. Cohen-Addad} et al., in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC '16, Cambridge, MA, USA, June 19--21, 2016. New York, NY: Association for Computing Machinery (ACM). 584--597 (2016; Zbl 1376.68171) Full Text: DOI
Klein, Philip N.; Mathieu, Claire; Zhou, Hang Correlation clustering and two-edge-connected augmentation for planar graphs. (English) Zbl 1355.68207 Mayr, Ernst W. (ed.) et al., 32nd international symposium on theoretical aspects of computer science, STACS’15, Garching, Germany, March 4–7, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-78-1). LIPIcs – Leibniz International Proceedings in Informatics 30, 554-567 (2015). MSC: 68R10 05C10 05C22 05C85 68W25 PDFBibTeX XMLCite \textit{P. N. Klein} et al., LIPIcs -- Leibniz Int. Proc. Inform. 30, 554--567 (2015; Zbl 1355.68207) Full Text: DOI
Fox, Kyle; Klein, Philip N.; Mozes, Shay A polynomial-time bicriteria approximation scheme for planar bisection. (English) Zbl 1321.68501 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 841-850 (2015). MSC: 68W25 05C10 05C22 05C70 05C85 PDFBibTeX XMLCite \textit{K. Fox} et al., in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 841--850 (2015; Zbl 1321.68501) Full Text: DOI arXiv
Klein, Philip N.; Marx, Daniel A subexponential parameterized algorithm for subset TSP on planar graphs. (English) Zbl 1423.68214 Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1812-1830 (2014). MSC: 68Q25 05C10 05C85 90C27 PDFBibTeX XMLCite \textit{P. N. Klein} and \textit{D. Marx}, in: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5--7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1812--1830 (2014; Zbl 1423.68214) Full Text: DOI
Eisenstat, David; Klein, Philip N.; Mathieu, Claire Approximating \(k\)-center in planar graphs. (English) Zbl 1421.68215 Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 617-627 (2014). MSC: 68W25 05C10 05C85 68W40 90B80 PDFBibTeX XMLCite \textit{D. Eisenstat} et al., in: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5--7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 617--627 (2014; Zbl 1421.68215) Full Text: DOI
Demaine, Erik D.; Hajiaghayi, Mohammadtaghi; Klein, Philip N. Node-weighted Steiner tree and group Steiner tree in planar graphs. (English) Zbl 1398.68667 ACM Trans. Algorithms 10, No. 3, Article No. 13, 20 p. (2014). MSC: 68W25 05C05 05C10 68R10 90C35 PDFBibTeX XMLCite \textit{E. D. Demaine} et al., ACM Trans. Algorithms 10, No. 3, Article No. 13, 20 p. (2014; Zbl 1398.68667) Full Text: DOI
Klein, Philip N.; Mozes, Shay; Sommer, Christian Structured recursive separator decompositions for planar graphs in linear time. (English) Zbl 1293.05066 Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 505-514 (2013). MSC: 05C10 05C70 05C85 68Q17 68Q25 PDFBibTeX XMLCite \textit{P. N. Klein} et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 505--514 (2013; Zbl 1293.05066) Full Text: DOI arXiv
Eisenstat, David; Klein, Philip; Mathieu, Claire An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. (English) Zbl 1421.68214 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 626-638 (2012). MSC: 68W25 05C10 05C85 68W40 PDFBibTeX XMLCite \textit{D. Eisenstat} et al., in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 626--638 (2012; Zbl 1421.68214) Full Text: arXiv Link
Klein, Philip N.; Marx, Dániel Solving planar \(k\)-terminal cut in \(O(n^{c \sqrt{k}})\) time. (English) Zbl 1272.68157 Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9–13, 2012. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-31593-0/pbk). Lecture Notes in Computer Science 7391, 569-580 (2012). MSC: 68Q25 05C10 05C40 68Q17 PDFBibTeX XMLCite \textit{P. N. Klein} and \textit{D. Marx}, Lect. Notes Comput. Sci. 7391, 569--580 (2012; Zbl 1272.68157) Full Text: DOI
Klein, Philip N.; Mozes, Shay; Weimann, Oren Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm. (English) Zbl 1300.05301 ACM Trans. Algorithms 6, No. 2, Article No. 30, 18 p. (2010). MSC: 05C85 05C10 05C12 05C20 05C38 68Q25 PDFBibTeX XMLCite \textit{P. N. Klein} et al., ACM Trans. Algorithms 6, No. 2, Article No. 30, 18 p. (2010; Zbl 1300.05301) Full Text: DOI
Klein, Philip; Mozes, Shay; Weimann, Oren Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n \log^2 n)\)-time algorithm. (English) Zbl 1423.05178 Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 236-245 (2009). MSC: 05C85 05C10 05C12 05C20 05C38 68Q25 PDFBibTeX XMLCite \textit{P. Klein} et al., in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4--6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 236--245 (2009; Zbl 1423.05178) Full Text: Link
Borradaile, Glencora; Klein, Philip; Mathieu, Claire An \(O(n\log n)\) approximation scheme for Steiner tree in planar graphs. (English) Zbl 1300.05294 ACM Trans. Algorithms 5, No. 3, Article No. 31, 31 p. (2009). MSC: 05C85 05C05 05C10 05C40 68Q17 68W25 PDFBibTeX XMLCite \textit{G. Borradaile} et al., ACM Trans. Algorithms 5, No. 3, Article No. 31, 31 p. (2009; Zbl 1300.05294) Full Text: DOI
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Klein, Philip N. Node-weighted Steiner tree and group Steiner tree in planar graphs. (English) Zbl 1248.68556 Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 328-340 (2009). MSC: 68W25 05C10 05C85 90C27 PDFBibTeX XMLCite \textit{E. D. Demaine} et al., Lect. Notes Comput. Sci. 5555, 328--340 (2009; Zbl 1248.68556) Full Text: DOI Link
Borradaile, Glencora; Kenyon-Mathieu, Claire; Klein, Philip A polynomial-time approximation scheme for Steiner tree in planar graphs. (English) Zbl 1302.05178 Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 1285-1294 (2007). MSC: 05C85 05C05 05C10 68W25 90C35 PDFBibTeX XMLCite \textit{G. Borradaile} et al., in: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7--9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 1285--1294 (2007; Zbl 1302.05178)
Borradaile, Glencora; Klein, Philip N.; Mathieu, Claire Steiner tree in planar graphs: an \(O(n\log n)\) approximation scheme with singly-exponential dependence on epsilon. (English) Zbl 1209.68633 Dehne, Frank (ed.) et al., Algorithms and data structures. 10th international workshop, WADS 2007, Halifax, Canada, August 15–17, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73948-7/pbk). Lecture Notes in Computer Science 4619, 275-286 (2007). MSC: 68W25 05C10 05C85 90C35 PDFBibTeX XMLCite \textit{G. Borradaile} et al., Lect. Notes Comput. Sci. 4619, 275--286 (2007; Zbl 1209.68633) Full Text: DOI
Klein, Philip N. A subset spanner for planar graphs, with application to subset TSP. (English) Zbl 1301.05335 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 749-756 (2006). MSC: 05C85 05C10 68Q25 68W25 90C27 90C35 PDFBibTeX XMLCite \textit{P. N. Klein}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 749--756 (2006; Zbl 1301.05335) Full Text: DOI
Klein, Philip N. Multiple-source shortest paths in planar graphs. (English) Zbl 1297.05059 Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 146-155 (2005). MSC: 05C10 05C38 05C85 68Q25 PDFBibTeX XMLCite \textit{P. N. Klein}, in: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23--25, 2005. New York, NY: ACM Press. 146--155 (2005; Zbl 1297.05059)
Klein, Philip; Rao, Satish; Rauch, Monika; Subramanian, Sairam Faster shortest-path algorithms for planar graphs. (English) Zbl 1345.05103 Proceedings of the 26th annual ACM symposium on theory of computing, STOC ’94, Montreal, Canada, May 23–25, 1994. New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-663-8). 27-37 (1994). MSC: 05C85 05C10 05C21 05C35 05C70 68Q25 PDFBibTeX XMLCite \textit{P. Klein} et al., in: Proceedings of the 26th annual ACM symposium on theory of computing, STOC '94, Montreal, Canada, May 23--25, 1994. New York, NY: Association for Computing Machinery (ACM). 27--37 (1994; Zbl 1345.05103) Full Text: DOI