×

Found 46 Documents (Results 1–46)

Isomorphisms of maps on the sphere. (English) Zbl 1468.05187

Cunningham, Gabriel (ed.) et al., Polytopes and discrete geometry. AMS special session, Northeastern University, Boston, MA, USA, April 21–22, 2018. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 764, 125-147 (2021).
PDFBibTeX XMLCite
Full Text: DOI

Polylogarithmic approximation for Euler genus on bounded degree graphs. (English) Zbl 1433.68299

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 164-175 (2019).
PDFBibTeX XMLCite
Full Text: DOI

Additive non-approximability of chromatic number in proper minor-closed classes. (English) Zbl 1499.68267

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 47, 12 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Combinatorial optimization and graph algorithms. Communications of NII Shonan meetings. (English) Zbl 1394.90011

Singapore: Springer (ISBN 978-981-10-6146-2/hbk; 978-981-10-6147-9/ebook). ix, 120 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract). (English) Zbl 1321.05063

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). 675-682 (2015).
MSC:  05C10 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deterministic global minimum cut of a simple graph in near-linear time. (English) Zbl 1321.05268

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

Coloring 3-colorable graphs with \(o(n^{1/5})\) colors. (English) Zbl 1359.05123

Mayr, Ernst W. (ed.) et al., 31st international symposium on theoretical aspects of computer science, STACS’ 14, Lyon, France, March 5–8, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-65-1). LIPIcs – Leibniz International Proceedings in Informatics 25, 458-469 (2014).
MSC:  05C85 05C15 68W25
PDFBibTeX XMLCite
Full Text: DOI

Embedding and canonizing graphs of bounded genus in logspace. (English) Zbl 1315.68254

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

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. (English) Zbl 1315.05132

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

Totally odd subdivisions and parity subdivisions: structures and coloring. (English) Zbl 1423.05175

Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1013-1029 (2013).
PDFBibTeX XMLCite
Full Text: DOI Link

List-coloring embedded graphs. (English) Zbl 1423.05063

Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1004-1012 (2013).
PDFBibTeX XMLCite
Full Text: DOI arXiv

5-coloring \(K_{3,k}\)-minor-free graphs. (English) Zbl 1423.05174

Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 985-1003 (2013).
PDFBibTeX XMLCite
Full Text: DOI

More compact oracles for approximate distances in undirected planar graphs. (English) Zbl 1423.68350

Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 550-563 (2013).
PDFBibTeX XMLCite
Full Text: DOI

Model checking for successor-invariant first-order logic on minor-closed graph classes. (English) Zbl 1366.68168

Proceedings of the 2013 28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, Tulane University, New Orleans, LA, USA, June 25–28, 2013. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-5020-6). 134-142 (2013).
PDFBibTeX XMLCite
Full Text: DOI

List-coloring graphs without subdivisions and without immersions. (English) Zbl 1425.05153

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). 1425-1435 (2012).
MSC:  05C85 05C15 68W25
PDFBibTeX XMLCite
Full Text: Link

The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. (English) Zbl 1292.68094

Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 160-169 (2011).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Finding topological subgraphs is fixed-parameter tractable. (English) Zbl 1288.05058

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 479-488 (2011).
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications. (English) Zbl 1288.05256

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 441-450 (2011).
PDFBibTeX XMLCite
Full Text: DOI

An (almost) linear time algorithm for odd cycles transversal. (English) Zbl 1288.05280

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). 365-378 (2010).
PDFBibTeX XMLCite

The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs. (English) Zbl 1288.05148

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). 345-353 (2010).
PDFBibTeX XMLCite

Decomposition, approximation, and coloring of odd-minor-free graphs. (English) Zbl 1288.05053

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). 329-344 (2010).
PDFBibTeX XMLCite

Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements. (English) Zbl 1288.05279

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). 318-328 (2010).
PDFBibTeX XMLCite

An \(O(\log n)\)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs. (English) Zbl 1305.68339

Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 274-286 (2010).
PDFBibTeX XMLCite
Full Text: DOI

Three-coloring triangle-free planar graphs in linear time. (English) Zbl 1423.05064

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

Additive approximation algorithms for list-coloring minor-closed class of graphs. (English) Zbl 1423.05176

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

List-color-critical graphs on a fixed surface. (English) Zbl 1423.05070

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). 1156-1165 (2009).
MSC:  05C15 05C10 05C85
PDFBibTeX XMLCite
Full Text: Link

Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. (English) Zbl 1423.05179

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

Hadwiger’s conjecture is decidable. (English) Zbl 1304.05047

Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 445-454 (2009).
MSC:  05C15 05C75 05C85
PDFBibTeX XMLCite
Full Text: DOI

Planarity allowing few error vertices in linear time. (English) Zbl 1292.68093

2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 639-648 (2009).
PDFBibTeX XMLCite
Full Text: DOI

Approximating list-coloring on a fixed surface. (English) Zbl 1153.05319

Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 333-344 (2008).
PDFBibTeX XMLCite
Full Text: DOI

Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs. (English) Zbl 1301.05334

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

Filter Results by …

Document Type

Database

all top 5

Year of Publication

all top 3

Main Field

Software