×

Found 1,015 Documents (Results 1–100)

NP-hardness of approximating meta-complexity: a cryptographic approach. (English) Zbl 07844654

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). 1067-1075 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Pandora Box problem with nonobligatory inspection: hardness and approximation scheme. (English) Zbl 07844631

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). 789-802 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Degreewidth: a new parameter for solving problems on tournaments. (English) Zbl 07842216

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, 246-260 (2023).
MSC:  68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Verification of NP-hardness reduction functions for exact lattice problems. (English) Zbl 07838497

Pientka, Brigitte (ed.) et al., Automated deduction – CADE 29. 29th international conference on automated deduction, Rome, Italy, July 1–4, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14132, 365-381 (2023).
MSC:  03B35 68V15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parity permutation pattern matching. (English) Zbl 07770307

Lin, Chun-Cheng (ed.) et al., WALCOM: algorithms and computation. 17th international conference and workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13973, 384-395 (2023).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI HAL

Interweaving real-time jobs with energy harvesting to maximize throughput. (English) Zbl 07770301

Lin, Chun-Cheng (ed.) et al., WALCOM: algorithms and computation. 17th international conference and workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13973, 305-316 (2023).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Constant-factor approximation algorithms for some maximin multi-clustering problems. (English) Zbl 1528.90279

Khachay, Michael (ed.) et al., Mathematical optimization theory and operations research. 22nd international conference, MOTOR 2023, Ekaterinburg, Russia, July 2–8, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13930, 85-100 (2023).
MSC:  90C47 68W25
PDFBibTeX XMLCite
Full Text: DOI

On the complexity of the storyplan problem. (English) Zbl 07727769

Angelini, Patrizio (ed.) et al., Graph drawing and network visualization. 30th international symposium, GD 2022, Tokyo, Japan, September 13–16, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13764, 304-318 (2023).
MSC:  68R10 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Hardness of bounding influence via graph modification. (English) Zbl 1531.68049

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, 129-143 (2023).
MSC:  68R10 68Q17
PDFBibTeX XMLCite
Full Text: DOI

The complexity of finding tangles. (English) Zbl 1529.68183

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, 3-17 (2023).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Exact algorithms and hardness results for geometric red-blue hitting set problem. (English) Zbl 1528.68387

Li, Minming (ed.) et al., Frontiers of algorithmic wisdom. International joint conference, IJTCS-FAW 2022, Hong Kong, China, August 15–19, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13461, 176-191 (2023).
MSC:  68U05 68Q17 68W40
PDFBibTeX XMLCite
Full Text: DOI

Wordle is NP-hard. (English) Zbl 07850172

Fraigniaud, Pierre (ed.) et al., 11th international conference on fun with algorithms, FUN 2022, Island of Favignana, Sicily, Italy, May 30 – June 3, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 226, Article 19, 8 p. (2022).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Reordering a tree according to an order on its leaves. (English) Zbl 07842485

Bannai, Hideo (ed.) et al., 33rd annual symposium on combinatorial pattern matching, CPM 2022, Prague, Czech Republic, June 27–29, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 223, Article 24, 15 p. (2022).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI

Rewriting with acyclic queries: mind your head. (English) Zbl 07838430

Aspnes, James (ed.) et al., 1st symposium on algorithmic foundations of dynamic networks, SAND 2022, virtual conference, March 28–30, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 221, Article 8, 20 p. (2022).
MSC:  68Mxx 68R10
PDFBibTeX XMLCite
Full Text: DOI

Rewriting with acyclic queries: mind your head. (English) Zbl 07836638

Olteanu, Dan (ed.) et al., 25th international conference on database theory, ICDT 2022, Edinburgh, UK, virtual conference, March 29 – April 1, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 220, Article 8, 20 p. (2022).
MSC:  68P15
PDFBibTeX XMLCite
Full Text: DOI

Maximally satisfying lower quotas in the hospitals/residents problem with ties. (English) Zbl 07836598

Berenbrink, Petra (ed.) et al., 39th international symposium on theoretical aspects of computer science, STACS 2022, Marseille, France, virtual conference, March 15–18, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 219, Article 31, 20 p. (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On computing optimal linear diagrams. (English) Zbl 1524.68433

Giardino, Valeria (ed.) et al., Diagrammatic representation and inference. 13th international conference, Diagrams 2022, Rome, Italy, September 14–16, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13462, 20-36 (2022).
MSC:  68W05 68Q17 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the intractability landscape of digraph intersection representations. (English) Zbl 07577705

Bazgan, Cristina (ed.) et al., Combinatorial algorithms. 33rd international workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13270, 270-284 (2022).
MSC:  68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

Biographic Reference