×

Found 34 Documents (Results 1–34)

Constant round distributed domination on graph classes with bounded expansion. (English) Zbl 07495148

Jurdziński, Tomasz (ed.) et al., Structural information and communication complexity. 28th international colloquium, SIROCCO 2021, Wrocław, Poland, June 28 – July 1, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12810, 334-351 (2021).
MSC:  68Mxx 68Q11 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the parameterized complexity of reconfiguration of connected dominating sets. (English) Zbl 07764115

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 24, 15 p. (2020).
MSC:  68Q25 68Q27 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

A general kernelization technique for domination and independence problems in sparse classes. (English) Zbl 07764102

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 11, 15 p. (2020).
MSC:  68Q25 68Q27 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the parameterized complexity of the expected coverage problem. (English) Zbl 07603924

Fernau, Henning, Computer science – theory and applications. 15th international computer science symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12159, 224-236 (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Decremental optimization of dominating sets under the reconfiguration framework. (English) Zbl 07600999

Gąsieniec, Leszek (ed.) et al., Combinatorial algorithms. 31st international workshop, IWOCA 2020, Bordeaux, France, June 8–10, 2020, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12126, 69-82 (2020).
MSC:  68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Domination above \(r\)-independence: does sparseness help? (English) Zbl 07561684

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 40, 13 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithmic properties of sparse digraphs. (English) Zbl 07559155

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 46, 20 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Progressive algorithms for domination and independence. (English) Zbl 07559136

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 27, 16 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness. (English) Zbl 1493.68398

D’Angelo, Gianlorenzo (ed.), 17th symposium on experimental algorithms, SEA 2018, June 27–29, 2018, L’Aquila, Italy. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 103, Article 14, 16 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lossy kernels for connected dominating set on sparse graphs. (English) Zbl 1487.68176

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 29, 15 p. (2018).
MSC:  68R10 05C69 68Q27
PDFBibTeX XMLCite
Full Text: DOI arXiv

On directed covering and domination problems. (English) Zbl 1457.05088

Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 45, 12 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Being even slightly shallow makes life hard. (English) Zbl 1441.68194

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 79, 13 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lossy kernels for hitting subgraphs. (English) Zbl 1441.68175

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 67, 14 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Reconfiguration on sparse graphs. (English) Zbl 1451.68134

Dehne, Frank (ed.) et al., Algorithms and data structures. 14th international symposium, WADS 2015, Victoria, BC, Canada, August 5–7, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9214, 506-517 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Year of Publication

Main Field

all top 3

Software