×

Found 21 Documents (Results 1–21)

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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).
PDFBibTeX XMLCite
Full Text: arXiv Link

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: Link

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).
PDFBibTeX XMLCite
Full Text: DOI Link

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).
PDFBibTeX XMLCite

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite

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).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

Main Field

Software