Pettie, Seth Sharp bounds on Davenport-Schinzel sequences of every order. (English) Zbl 1426.68232 J. ACM 62, No. 5, Article No. 36, 40 p. (2015). MSC: 68R15 05A05 68U05 PDFBibTeX XMLCite \textit{S. Pettie}, J. ACM 62, No. 5, Article No. 36, 40 p. (2015; Zbl 1426.68232) Full Text: DOI
Pettie, Seth Sharp bounds on formation-free sequences. (English) Zbl 1371.68224 Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 592-604 (2015). MSC: 68R15 PDFBibTeX XMLCite \textit{S. Pettie}, in: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4--6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 592--604 (2015; Zbl 1371.68224) Full Text: DOI
Pettie, Seth Three generalizations of Davenport-Schinzel sequences. (English) Zbl 1329.05010 SIAM J. Discrete Math. 29, No. 4, 2189-2238 (2015). MSC: 05A05 05A15 68R15 68R05 PDFBibTeX XMLCite \textit{S. Pettie}, SIAM J. Discrete Math. 29, No. 4, 2189--2238 (2015; Zbl 1329.05010) Full Text: DOI arXiv
Pettie, Seth Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. (English) Zbl 1323.05123 J. Graph Algorithms Appl. 19, No. 1, 375-391 (2015). MSC: 05C85 05C05 68W20 PDFBibTeX XMLCite \textit{S. Pettie}, J. Graph Algorithms Appl. 19, No. 1, 375--391 (2015; Zbl 1323.05123) Full Text: DOI
Pettie, Seth Sharp bounds on Davenport-Schinzel sequences of every order. (English) Zbl 1305.68093 Proceedings of the 29th annual symposium on computational geometry, SoCG 2013, Rio de Janeiro, Brazil, June 17–20, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2031-3). 319-328 (2013). MSC: 68Q17 05D99 11B50 68R05 68U05 PDFBibTeX XMLCite \textit{S. Pettie}, in: Proceedings of the 29th annual symposium on computational geometry, SoCG 2013, Rio de Janeiro, Brazil, June 17--20, 2013. New York, NY: Association for Computing Machinery (ACM). 319--328 (2013; Zbl 1305.68093) Full Text: DOI arXiv
Pettie, S. A simple reduction from maximum weight matching to maximum cardinality matching. (English) Zbl 1248.05161 Inf. Process. Lett. 112, No. 23, 893-898 (2012). MSC: 05C70 05C35 05C85 PDFBibTeX XMLCite \textit{S. Pettie}, Inf. Process. Lett. 112, No. 23, 893--898 (2012; Zbl 1248.05161) Full Text: DOI
Pettie, Seth On the structure and composition of forbidden sequences, with geometric applications. (English) Zbl 1283.68277 Proceedings of the 27th annual symposium on computational geometry, SoCG 2011, Paris, France, June 13–15, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0682-9). 370-379 (2011). MSC: 68R15 05A05 68W05 68Q17 PDFBibTeX XMLCite \textit{S. Pettie}, in: Proceedings of the 27th annual symposium on computational geometry, SoCG 2011, Paris, France, June 13--15, 2011. New York, NY: Association for Computing Machinery (ACM). 370--379 (2011; Zbl 1283.68277) Full Text: DOI Link
Pettie, Seth Degrees of nonlinearity in forbidden 0-1 matrix problems. (English) Zbl 1239.05028 Discrete Math. 311, No. 21, 2396-2410 (2011). MSC: 05B20 05A05 05D10 PDFBibTeX XMLCite \textit{S. Pettie}, Discrete Math. 311, No. 21, 2396--2410 (2011; Zbl 1239.05028) Full Text: DOI
Pettie, Seth Origins of nonlinearity in Davenport-Schinzel sequences. (English) Zbl 1233.05019 SIAM J. Discrete Math. 25, No. 1, 211-233 (2011). MSC: 05A05 05D99 68R05 PDFBibTeX XMLCite \textit{S. Pettie}, SIAM J. Discrete Math. 25, No. 1, 211--233 (2011; Zbl 1233.05019) Full Text: DOI
Pettie, S. Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts. (English) Zbl 1227.68087 J. Comb. Theory, Ser. A 118, No. 6, 1863-1895 (2011). MSC: 68R15 05A05 05D99 PDFBibTeX XMLCite \textit{S. Pettie}, J. Comb. Theory, Ser. A 118, No. 6, 1863--1895 (2011; Zbl 1227.68087) Full Text: DOI
Pettie, Seth Applications of forbidden 0-1 matrices to search tree and path compression-based data structures. (English) Zbl 1288.68052 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 1457-1467 (2010). MSC: 68P05 68W40 68Q17 PDFBibTeX XMLCite \textit{S. Pettie}, in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1457--1467 (2010; Zbl 1288.68052)
Pettie, Seth On nonlinear forbidden 0–1 matrices, a refutation of a Füredi-Hajnal conjecture. (English) Zbl 1288.05033 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 875-885 (2010). MSC: 05B20 05D99 05C50 PDFBibTeX XMLCite \textit{S. Pettie}, in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 875--885 (2010; Zbl 1288.05033)
Pettie, Seth Distributed algorithms for ultrasparse spanners and linear size skeletons. (English) Zbl 1267.68314 Distrib. Comput. 22, No. 3, 147-166 (2010). MSC: 68W15 05C85 PDFBibTeX XMLCite \textit{S. Pettie}, Distrib. Comput. 22, No. 3, 147--166 (2010; Zbl 1267.68314) Full Text: DOI
Pettie, Seth Low distortion spanners. (English) Zbl 1298.05307 ACM Trans. Algorithms 6, No. 1, Article No. 7, 22 p. (2009). MSC: 05C85 05C10 05C12 68R10 PDFBibTeX XMLCite \textit{S. Pettie}, ACM Trans. Algorithms 6, No. 1, Article No. 7, 22 p. (2009; Zbl 1298.05307) Full Text: DOI
Pettie, Seth Distributed algorithms for ultrasparse spanners and linear size skeletons. (English) Zbl 1301.68259 Proceedings of the 27th annual ACM symposium on principles of distributed computing, PODC ’08, Toronto, Canada, August 18–21, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-59593-989-0). 253-262 (2008). MSC: 68W15 05C85 68M14 68Q17 68R10 68U05 68W40 PDFBibTeX XMLCite \textit{S. Pettie}, in: Proceedings of the 27th annual ACM symposium on principles of distributed computing, PODC '08, Toronto, Canada, August 18--21, 2008. New York, NY: Association for Computing Machinery (ACM). 253--262 (2008; Zbl 1301.68259) Full Text: DOI
Pettie, Seth Splay trees, Davenport-Schinzel sequences, and the Deque conjecture. (English) Zbl 1192.68186 Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 1115-1124 (2008). MSC: 68P05 68Q25 05C85 PDFBibTeX XMLCite \textit{S. Pettie}, in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20--22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 1115--1124 (2008; Zbl 1192.68186)
Pettie, Seth Low distortion spanners. (English) Zbl 1171.68641 Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocław, Poland, July 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 78-89 (2007). MSC: 68R10 05C83 PDFBibTeX XMLCite \textit{S. Pettie}, Lect. Notes Comput. Sci. 4596, 78--89 (2007; Zbl 1171.68641) Full Text: DOI
Pettie, Seth An inverse-Ackermann type lower bound for online minimum spanning tree verification. (English) Zbl 1121.05067 Combinatorica 26, No. 2, 207-230 (2006). Reviewer: Stanislav Jendrol’ (Košice) MSC: 05C38 68R10 68Q17 PDFBibTeX XMLCite \textit{S. Pettie}, Combinatorica 26, No. 2, 207--230 (2006; Zbl 1121.05067) Full Text: DOI
Pettie, Seth Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. (English) Zbl 1175.68549 Deng, Xiaotie (ed.) et al., Algorithms and computation. 16th international symposium, ISAAC 2005, Sanya, Hainan, China, December 19–21, 2005. Proceedings. Berlin: Springer (ISBN 3-540-30935-7/pbk). Lecture Notes in Computer Science 3827, 964-973 (2005). MSC: 68W05 68P05 68Q25 90C35 PDFBibTeX XMLCite \textit{S. Pettie}, Lect. Notes Comput. Sci. 3827, 964--973 (2005; Zbl 1175.68549) Full Text: DOI arXiv
Pettie, Seth A new approach to all-pairs shortest paths on real-weighted graphs. (English) Zbl 1071.68084 Theor. Comput. Sci. 312, No. 1, 47-74 (2004). MSC: 68R10 05C85 68Q25 68W25 PDFBibTeX XMLCite \textit{S. Pettie}, Theor. Comput. Sci. 312, No. 1, 47--74 (2004; Zbl 1071.68084) Full Text: DOI
Pettie, Seth A faster all-pairs shortest path algorithm for real-weighted sparse graphs. (English) Zbl 1056.68111 Widmayer, Peter (ed.) et al., Automata, languages and programming. 29th international colloquium, ICALP 2002, Málaga, Spain, July 8–13, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43864-5). Lect. Notes Comput. Sci. 2380, 85-97 (2002). MSC: 68R10 05C85 68Q25 PDFBibTeX XMLCite \textit{S. Pettie}, Lect. Notes Comput. Sci. 2380, 85--97 (2002; Zbl 1056.68111) Full Text: Link
Pettie, Seth On the comparison-addition complexity of all-pairs shortest paths. (English) Zbl 1019.68081 Bose, Prosenjit (ed.) et al., Algorithms and computation. 13th international symposium, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2518, 32-43 (2002). MSC: 68R10 68W05 68Q25 05C85 05C38 PDFBibTeX XMLCite \textit{S. Pettie}, Lect. Notes Comput. Sci. 2518, 32--43 (2002; Zbl 1019.68081) Full Text: Link