×

Found 312 Documents (Results 1–100)

Random graph matching at Otter’s threshold via counting chandeliers. (English) Zbl 07844676

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 1345-1356 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Removing additive structure in 3SUM-based reductions. (English) Zbl 07844599

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 405-418 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Proportionally fair matching with multiple groups. (English) Zbl 07842199

Paulusma, Daniël (ed.) et al., Graph-theoretic concepts in computer science. 49th international workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 14093, 1-15 (2023).
MSC:  68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the power of threshold-based algorithms for detecting cycles in the CONGEST model. (English) Zbl 07786531

Rajsbaum, Sergio (ed.) et al., Structural information and communication complexity. 30th international colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6–9, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13892, 459-481 (2023).
MSC:  68Mxx 68Q11 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Inapproximability of shortest paths on perfect matching polytopes. (English) Zbl 07763008

Del Pia, Alberto (ed.) et al., Integer programming and combinatorial optimization. 24th international conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13904, 72-86 (2023).
MSC:  90C35
PDFBibTeX XMLCite
Full Text: DOI arXiv

Balanced substructures in bicolored graphs. (English) Zbl 1531.68047

Gąsieniec, Leszek (ed.), SOFSEM 2023: theory and practice of computer science. 48th international conference on current trends in theory and practice of computer science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15–18, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13878, 177-191 (2023).
MSC:  68R10 05C15 68Q27
PDFBibTeX XMLCite
Full Text: DOI

On the approximability of path and cycle problems in arc-dependent networks. (English) Zbl 07683180

Balachandran, Niranjan (ed.) et al., Algorithms and discrete applied mathematics. 8th international conference, CALDAM 2022, Puducherry, India, February 10–12, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13179, 292-304 (2022).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio. (English) Zbl 07632760

Cerejeiras, Paula (ed.) et al., Mathematical analysis, its applications and computation. ISAAC 2019. Selected papers based on the presentations at the 12th international congress, Aveiro, Portugal, July 29 – August 2, 2019. Cham: Springer. Springer Proc. Math. Stat. 385, 1-50 (2022).
MSC:  62H15 62H25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Finding colorful paths in temporal graphs. (English) Zbl 1506.05198

Benito, Rosa Maria (ed.) et al., Complex networks & their applications X. Volume 1. Proceedings of the 10th international conference, COMPLEX NETWORKS 2021, Madrid, Spain, November 30 – December 2, 2021. Cham: Springer. Stud. Comput. Intell. 1015, 553-565 (2022).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized complexity of reconfiguration of atoms. (English) Zbl 07556577

Mutzel, Petra (ed.) et al., WALCOM: algorithms and computation. 16th international conference and workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13174, 263-274 (2022).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Preprocessing to reduce the search space: antler structures for feedback vertex set. (English) Zbl 07538563

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, 1-14 (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

Parameterizing role coloring on forests. (English) Zbl 1490.68163

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 308-321 (2021).
PDFBibTeX XMLCite
Full Text: DOI

To close is easier than to open: dual parameterization to \(k\)-median. (English) Zbl 07495122

Kaklamanis, Christos (ed.) et al., Approximation and online algorithms. 18th international workshop, WAOA 2020, virtual event, September 9–10, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12806, 113-126 (2021).
MSC:  68W25 68W27
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

On the parameterized complexity of maximum degree contraction problem. (English) Zbl 07764117

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

On the fine-grained parameterized complexity of partial scheduling to minimize the makespan. (English) Zbl 07764116

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

The maximum binary tree problem. (English) Zbl 07651169

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

Parameterized complexity of \((A,\ell)\)-path packing. (English) Zbl 07600997

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, 43-55 (2020).
MSC:  68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Finding small satisfying assignments faster than brute force: a fine-grained perspective into Boolean constraint satisfaction. (English) Zbl 07561755

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 27, 28 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized complexity of maximum edge colorable subgraph. (English) Zbl 07336139

Kim, Donghyun (ed.) et al., Computing and combinatorics. 26th international conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12273, 615-626 (2020).
MSC:  68Rxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs. (English) Zbl 1516.68069

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

Packing arc-disjoint cycles in tournaments. (English) Zbl 07561671

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

Near-linear time algorithm for \(n\)-fold ILPs via color coding. (English) Zbl 07561568

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

Decomposition of map graphs with applications. (English) Zbl 07561553

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 60, 15 p. (2019).
MSC:  68Nxx 68Qxx
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

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field