×

Found 59 Documents (Results 1–59)

Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs. (English) Zbl 07538586

Kowalik, Łukasz (ed.) et al., Graph-theoretic concepts in computer science. 47th international workshop, WG 2021, Warsaw, Poland, June 23–25, 2021. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12911, 308-320 (2021).
MSC:  68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

An algorithmic meta-theorem for graph modification to planarity and FOL. (English) Zbl 07651190

Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 51, 17 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Modification to planarity is fixed parameter tractable. (English) Zbl 07559137

Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 28, 17 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Partial complementation of graphs. (English) Zbl 1477.68225

Eppstein, David (ed.), 16th Scandinavian symposium and workshops on algorithm theory. SWAT 2018, June 18–20, 2018, Malmö University, Malmö, Sweden. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 101, Article 21, 13 p. (2018).
MSC:  68R10 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Structured connectivity augmentation. (English) Zbl 1441.05125

Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 29, 13 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. (English) Zbl 1354.68120

Portier, Natacha (ed.) et al., 30th international symposium on theoretical aspects of computer science, STACS’ 13, Kiel, Germany, February 27 – March 2, 2013. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-50-7). LIPIcs – Leibniz International Proceedings in Informatics 20, 92-103 (2013).
MSC:  68Q25 05C69 05C83
PDFBibTeX XMLCite
Full Text: DOI arXiv

Linear kernels for (connected) dominating set on \(H\)-minor-free graphs. (English) Zbl 1421.68078

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). 82-93 (2012).
MSC:  68Q25 05C69 05C83
PDFBibTeX XMLCite
Full Text: Link

Approximation algorithms for domination search. (English) Zbl 1314.68396

Jansen, Klaus (ed.) et al., Approximation and online algorithms. 8th international workshop, WAOA 2010, Liverpool, UK, September 9–10, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-18317-1/pbk). Lecture Notes in Computer Science 6534, 130-141 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Bidimensionality and kernels. (English) Zbl 1288.68116

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). 503-510 (2010).
PDFBibTeX XMLCite
Full Text: arXiv

Fast minor testing in planar graphs. (English) Zbl 1287.05141

de Berg, Mark (ed.) et al., Algorithms – ESA 2010. 18th annual European symposium, Liverpool, UK, September 6–8, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-15774-5/pbk). Lecture Notes in Computer Science 6346, 97-109 (2010).
PDFBibTeX XMLCite
Full Text: DOI Link

Faster parameterized algorithms for minor containment. (English) Zbl 1285.68206

Kaplan, Haim (ed.), Algorithm theory – SWAT 2010. 12th Scandinavian symposium and workshops on algorithm theory, Bergen, Norway, June 21–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13730-3/pbk). Lecture Notes in Computer Science 6139, 322-333 (2010).
PDFBibTeX XMLCite
Full Text: DOI

(Meta) kernelization. (English) Zbl 1292.68089

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). 629-638 (2009).
MSC:  68Q25 68R10
PDFBibTeX XMLCite
Full Text: DOI

Approximating acyclicity parameters of sparse hypergraphs. (English) Zbl 1236.68089

Albers, Susanne (ed.) et al., STACS 2009. 26th international symposium on theoretical aspects of computer science, Freiburg, Germany, February 26–28, 2009. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-09-5). LIPIcs – Leibniz International Proceedings in Informatics 3, 445-456, electronic only (2009).
PDFBibTeX XMLCite
Full Text: DOI Link

Contraction bidimensionality: the accurate picture. (English) Zbl 1256.05202

Fiat, Amos (ed.) et al., Algorithms – ESA 2009. 17th annual European symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04127-3/pbk). Lecture Notes in Computer Science 5757, 706-717 (2009).
PDFBibTeX XMLCite
Full Text: DOI Link

Catalan structures and dynamic programming in \(H\)-minor-free graphs. (English) Zbl 1192.05155

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). 631-640 (2008).
MSC:  05C85 05C83 68Q25
PDFBibTeX XMLCite

Subexponential parameterized algorithms. (English) Zbl 1171.68875

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, 15-27 (2007).
MSC:  68W40 68Q25 68R10
PDFBibTeX XMLCite
Full Text: DOI

On exact algorithms for treewidth. (English) Zbl 1131.68481

Azar, Yossi (ed.) et al., Algorithms – ESA 2006. 14th annual European symposium, Zurich, Switzerland, September 11–13, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-38875-3/pbk). Lecture Notes in Computer Science 4168, 672-683 (2006).
PDFBibTeX XMLCite
Full Text: DOI Link

Fast subexponential algorithm for non-local problems on graphs of bounded genus. (English) Zbl 1141.05338

Arge, Lars (ed.) et al., Algorithm theory – SWAT 2006. 10th Scandinavian workshop on algorithm theory, Riga, Latvia, July 6–8, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-35753-7/pbk). Lecture Notes in Computer Science 4059, 172-183 (2006).
MSC:  05C85 68Q25 90C35
PDFBibTeX XMLCite
Full Text: DOI

Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs. (English) Zbl 1318.05076

Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11–13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-558-X). 830-839 (2004).
PDFBibTeX XMLCite

Bidimensional parameters and local treewidth. (English) Zbl 1196.68169

Farach-Colton, Martin (ed.), LATIN 2004: Theoretical informatics. 6th Latin American symposium, Buenos Aires, Argentina, April 5–8, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21258-2/pbk). Lecture Notes in Computer Science 2976, 109-118 (2004).
MSC:  68R10 05C69 68Q25
PDFBibTeX XMLCite
Full Text: DOI

A simple and fast approach for solving problems on planar graphs. (English) Zbl 1122.68480

Diekert, Volker (ed.) et al., STACS 2004. 21st annual symposium on theoretical aspects of computer science, Montpellier, France, March 25–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21236-1/pbk). Lecture Notes in Computer Science 2996, 56-67 (2004).
MSC:  68R10 05C85 68Q25
PDFBibTeX XMLCite
Full Text: DOI

A 3-approximation for the pathwidth of Halin graphs. (English) Zbl 1152.05375

Liberti, Leo (ed.) et al., Workshop on graphs and combinatorial optimization. Papers from the workshop, Como, Italy, May 31, 2004. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 17, 157-162 (2004).
MSC:  05C85 68W25
PDFBibTeX XMLCite
Full Text: DOI

Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. (English) Zbl 1099.68077

Díaz, Josep (ed.) et al., Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12–16, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22849-7/pbk). Lecture Notes in Computer Science 3142, 581-592 (2004).
PDFBibTeX XMLCite
Full Text: DOI

Dominating sets and local treewidth. (English) Zbl 1266.05164

Di Battista, Giuseppe (ed.) et al., Algorithms – ESA 2003. 11th annual European symposium, Budapest, Hungary, September 16–19, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20064-9/pbk). Lect. Notes Comput. Sci. 2832, 221-229 (2003).
MSC:  05C85 05C69 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Dominating sets in planar graphs: Branch-width and exponential speed-up. (English) Zbl 1094.68610

Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12–14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics (ISBN 0-89871-538-5/pbk). 168-177 (2003).
MSC:  68R10 05C83 05C85
PDFBibTeX XMLCite

Fixed-parameter algorithms for the \((k,r)\)-center in planar graphs and map graphs. (English) Zbl 1039.68093

Baeten, Jos C. M. (ed.) et al., Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 – July 4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40493-7/pbk). Lect. Notes Comput. Sci. 2719, 829-844 (2003).
PDFBibTeX XMLCite
Full Text: Link

On the monotonicity of games generated by symmetric submodular functions. (English) Zbl 1042.68631

Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 27th international workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42707-4). Lect. Notes Comput. Sci. 2204, 177-188 (2001).
MSC:  68R10 91A80
PDFBibTeX XMLCite
Full Text: Link

Filter Results by …

Document Type

Database

all top 5

Year of Publication

all top 3

Main Field

Biographic Reference