×

Found 287 Documents (Results 1–100)

Tree decompositions meet induced matchings: beyond Max Weight Independent Set. arXiv:2402.15834

Preprint, arXiv:2402.15834 [cs.DS] (2024).
BibTeX Cite
Full Text: arXiv

Vertex deletion into bipartite permutation graphs. (English) Zbl 07764096

Cao, Yixin (ed.) et al., 15th international symposium on parameterized and exact computation, IPEC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 180, Article 5, 16 p. (2020).
PDFBibTeX XMLCite
Full Text: DOI

Graph square roots of small distance from degree one graphs. (English) Zbl 07600769

Kohayakawa, Yoshiharu (ed.) et al., Latin 2020: theoretical informatics. 14th Latin American symposium, São Paulo, Brazil, January 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12118, 116-128 (2020).
MSC:  68Qxx 68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Elimination distance to bounded degree on planar graphs. (English) Zbl 07559436

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 65, 12 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithms for the rainbow vertex coloring problem on graph classes. (English) Zbl 1517.05168

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 63, 13 p. (2020).
PDFBibTeX XMLCite
Full Text: DOI

Structural parameterizations of clique coloring. (English) Zbl 1518.68269

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 49, 15 p. (2020).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Finding optimal solutions with neighborly help. (English) Zbl 07561722

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 78, 14 p. (2019).
MSC:  68R10 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

The complexity of homomorphism indistinguishability. (English) Zbl 07561698

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 54, 13 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI

Constrained representations of map graphs and half-squares. (English) Zbl 07561657

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 13, 15 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI

Minimal separators in graph classes defined by small forbidden induced subgraphs. (English) Zbl 07173314

Sau, Ignasi (ed.) et al., Graph-theoretic concepts in computer science. 45th international workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019. Revised papers. Cham: Springer. Lect. Notes Comput. Sci. 11789, 379-391 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion. (English) Zbl 1477.68131

Sau, Ignasi (ed.) et al., Graph-theoretic concepts in computer science. 45th international workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019. Revised papers. Cham: Springer. Lect. Notes Comput. Sci. 11789, 106-119 (2019).
MSC:  68Q27 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

The parameterized complexity of dominating set and friends revisited for structured graphs. (English) Zbl 1533.68260

van Bevern, René (ed.) et al., Computer science – theory and applications. 14th international computer science symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11532, 299-310 (2019).
MSC:  68R10 05C69 68Q27
PDFBibTeX XMLCite
Full Text: DOI

Polynomial kernels for hitting forbidden minors under structural parameterizations. (English) Zbl 1524.68233

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 48, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

The robustness of LWPP and WPP, with an application to graph reconstruction. (English) Zbl 1512.68103

Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 51, 14 p. (2018).
MSC:  68Q15 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width. (English) Zbl 1487.68180

Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 42, 14 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Smaller parameters for vertex cover kernelization. (English) Zbl 1443.68072

Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 20, 12 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? (English) Zbl 1443.68071

Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 10, 13 p. (2018).
MSC:  68Q27 68Q17 68R10
PDFBibTeX XMLCite
Full Text: DOI

Reconfiguring spanning and induced subgraphs. (English) Zbl 1436.68136

Wang, Lusheng (ed.) et al., Computing and combinatorics. 24th international conference, COCOON 2018, Qing Dao, China, July 2–4, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10976, 428-440 (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithmic information distortions and incompressibility in uniform multidimensional networks. arXiv:1810.11719

Preprint, arXiv:1810.11719 [cs.DM] (2018).
BibTeX Cite
Full Text: arXiv

Neighborhood complexity and kernelization for nowhere dense classes of graphs. (English) Zbl 1441.68176

Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 63, 14 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Structural parameterizations of feedback vertex set. (English) Zbl 1390.68352

Guo, Jiong (ed.) et al., 11th international symposium on parameterized and exact computation (IPEC 2016), Aarhus, Denmark, August 24–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-023-1). LIPIcs – Leibniz International Proceedings in Informatics 63, Article 21, 16 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Treedepth parameterized by vertex cover number. (English) Zbl 1398.68247

Guo, Jiong (ed.) et al., 11th international symposium on parameterized and exact computation (IPEC 2016), Aarhus, Denmark, August 24–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-023-1). LIPIcs – Leibniz International Proceedings in Informatics 63, Article 18, 11 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Hardness and structural results for half-squares of restricted tree convex bipartite graphs. (English) Zbl 1431.68097

Cao, Yixin (ed.) et al., Computing and combinatorics. 23rd international conference, COCOON 2017, Hong Kong, China, August 3–5, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10392, 359-370 (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Enumeration of maximal irredundant sets for claw-free graphs. (English) Zbl 1441.05015

Fotakis, Dimitris (ed.) et al., Algorithms and complexity. 10th international conference, CIAC 2017, Athens, Greece, May 24–26, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10236, 297-309 (2017).
PDFBibTeX XMLCite
Full Text: DOI

Descriptive complexity, canonisation, and definable graph structure theory. (English) Zbl 1530.68007

Lecture Notes in Logic 47. Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL) (ISBN 978-1-107-01452-7/hbk; 978-1-139-02886-8/ebook). ix, 543 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Structural control in weighted voting games. (English) Zbl 1398.91046

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 80, 15 p. (2016).
MSC:  91A12 68Q17 91B12
PDFBibTeX XMLCite
Full Text: DOI

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. (English) Zbl 1398.68228

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 34, 14 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software