×

Found 331 Documents (Results 1–100)

On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves. (English) Zbl 07745718

Mavronicolas, Marios (ed.), Algorithms and complexity. 13th international conference, CIAC 2023, Larnaca, Cyprus, June 13–16, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13898, 353-367 (2023).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Parameterized complexity of set-restricted disjoint paths on chordal graphs. (English) Zbl 07615736

Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 17th international computer science symposium in Russia, CSR 2022, virtual event, June 29 – July 1, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13296, 152-169 (2022).
MSC:  68Q27 68R10
PDFBibTeX XMLCite
Full Text: DOI

Lossy kernelization of same-size clustering. (English) Zbl 07615733

Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 17th international computer science symposium in Russia, CSR 2022, virtual event, June 29 – July 1, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13296, 96-114 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. arXiv:2211.01723

Preprint, arXiv:2211.01723 [cs.LO] (2022).
BibTeX Cite
Full Text: arXiv

ETH tight algorithms for geometric intersection graphs: now in polynomial space. (English) Zbl 07799599

Bojańczyk, Mikołaj (ed.) et al., 41st IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2021, virtual conference, December 15–17, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 213, Article 21, 16 p. (2021).
MSC:  68N30 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Partitioning \(H\)-free graphs of bounded diameter. (English) Zbl 07788594

Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 21, 14 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

EPTAS for k-means clustering of affine subspaces. (English) Zbl 07788495

Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2649-2659 (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized complexity of feature selection for categorical data clustering. (English) Zbl 07724187

Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 14, 14 p. (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Acyclic, star, and injective colouring: bounding the diameter. (English) Zbl 07538588

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, 336-348 (2021).
MSC:  68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

Parameterized complexity of categorical clustering with size constraints. (English) Zbl 07498691

Lubiw, Anna (ed.) et al., Algorithms and data structures. 17th international symposium, WADS 2021, virtual event, August 9–11, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12808, 385-398 (2021).
MSC:  68P05 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. (English) Zbl 1482.68023

LIPIcs – Leibniz International Proceedings in Informatics 214. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-216-7). xvii, 35 articles, not consecutively paged, electronic only, open access (2021).
PDFBibTeX XMLCite
Full Text: DOI Link

Diverse pairs of matchings. (English) Zbl 07765384

Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 26, 12 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized complexity of directed spanner problems. (English) Zbl 07764103

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

Recognizing proper tree-graphs. (English) Zbl 07764099

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

Parameterized complexity of PCA (Invited talk). (English) Zbl 07759269

Albers, Susanne (ed.), 17th Scandinavian symposium and workshops on algorithm theory, SWAT 2020, Tórshavn, Faroe Islands, June 22–24, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 162, Article 1, 5 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Low-rank binary matrix approximation in column-sum norm. (English) Zbl 07758334

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 32, 18 p. (2020).
MSC:  68W20 68W25 90C27
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

On the complexity of recovering incidence matrices. (English) Zbl 07651189

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 50, 13 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Subexponential parameterized algorithms and kernelization on almost chordal graphs. (English) Zbl 07651188

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 49, 17 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Kernelization of Whitney switches. (English) Zbl 07651187

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 48, 19 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Parameterization above a multiplicative guarantee. (English) Zbl 07650387

Vidick, Thomas (ed.), 11th innovations in theoretical computer science conference, ITCS 2020, Seattle, Washington, USA, January 12–14, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 151, Article 39, 13 p. (2020).
MSC:  68Qxx
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

Graph Hamiltonicity parameterized by proper interval deletion set. (English) Zbl 07600768

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, 104-115 (2020).
MSC:  68Qxx 68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Hitting topological minor models in planar graphs is fixed parameter tractable. (English) Zbl 07304079

Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 931-950 (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized \(k\)-clustering: tractability island. (English) Zbl 07650311

Chattopadhyay, Arkadev (ed.) et al., 39th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2019, Bombay, India, December 11–13, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 150, Article 14, 15 p. (2019).
MSC:  68N30 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Cyclability in graph classes. (English) Zbl 07650249

Lu, Pinyan (ed.) et al., 30th international symposium on algorithms and computation, ISAAC 2019, Shanghai University of Finance and Economics, Shanghai, China, December 8–11, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 149, Article 16, 13 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Clustering to given connectivities. (English) Zbl 07650226

Jansen, Bart M. P. (ed.) et al., 14th international symposium on parameterized and exact computation, IPEC 2019, Munich, Germany, September 11–13, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 148, Article 18, 17 p. (2019).
MSC:  68Q25 68Q27 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Covering vectors by spaces in perturbed graphic matroids and their duals. (English) Zbl 07561552

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 59, 13 p. (2019).
MSC:  68Nxx 68Qxx
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

Going far from degeneracy. (English) Zbl 07525484

Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 47, 14 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Kernelization of graph Hamiltonicity: proper \(H\)-graphs. (English) Zbl 1476.68197

Friggstad, Zachary (ed.) et al., Algorithms and data structures. 16th international symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11646, 296-310 (2019).
PDFBibTeX XMLCite
Full Text: DOI

On the tractability of optimization problems on \(H\)-graphs. (English) Zbl 1524.68228

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

Parameterized low-rank binary matrix approximation. (English) Zbl 1499.68151

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 53, 16 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Parameterized aspects of strong subgraph closure. (English) Zbl 1442.68169

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 23, 13 p. (2018).
MSC:  68R10 68Q27
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

Finding connected secluded subgraphs. (English) Zbl 1443.68129

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

Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth. (English) Zbl 1403.68164

Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 262-273 (2018).
PDFBibTeX XMLCite
Full Text: Link

Covering vectors by spaces: regular matroids. (English) Zbl 1441.68106

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 56, 15 p. (2017).
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

Spanning circuits in regular matroids. (English) Zbl 1410.68164

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1433-1441 (2017).
MSC:  68Q25 05B35 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Enumeration and maximum number of maximal irredundant sets for chordal graphs. (English) Zbl 1483.05180

Bodlaender, Hans L. (ed.) et al., Graph-theoretic concepts in computer science. 43rd international workshop, WG 2017, Eindhoven, The Netherlands, June 21–23, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10520, 289-302 (2017).
MSC:  05C85 05C69 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. (English) Zbl 1421.68081

Bodlaender, Hans L. (ed.) et al., Graph-theoretic concepts in computer science. 43rd international workshop, WG 2017, Eindhoven, The Netherlands, June 21–23, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10520, 275-288 (2017).
PDFBibTeX XMLCite
Full Text: DOI Link

Surjective \(H\)-colouring: new hardness results. (English) Zbl 1489.68192

Kari, Jarkko (ed.) et al., Unveiling dynamics and complexity. 13th conference on computability in Europe, CiE 2017, Turku, Finland, June 12–16, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10307, 270-281 (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field