×

Found 683 Documents (Results 1–100)

A walk through combinatorics. An introduction to enumeration and graph theory and selected other topics. 5th edition. (English) Zbl 1521.05001

Singapore: World Scientific (ISBN 978-981-12-7784-9/hbk; 978-981-12-7786-3/ebook). xxi, 613 p. (2024).
PDFBibTeX XMLCite
Full Text: DOI

Discovering event queries from traces: laying foundations for subsequence-queries with wildcards and gap-size constraints. (English) Zbl 07836648

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 18, 21 p. (2022).
MSC:  68P15
PDFBibTeX XMLCite
Full Text: DOI

Quantum time complexity and algorithms for pattern matching on labeled graphs. (English) Zbl 1525.68063

Arroyuelo, Diego (ed.) et al., String processing and information retrieval. 29th international symposium, SPIRE 2022, Concepción, Chile, November 8–10, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13617, 303-314 (2022).
MSC:  68Q12 68R10
PDFBibTeX XMLCite
Full Text: DOI

The complexity of approximate pattern matching on de Bruijn graphs. (English) Zbl 1494.92086

Pe’er, Itsik (ed.), Research in computational molecular biology. 26th annual international conference, RECOMB 2022, San Diego, CA, USA, May 22–25, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13278, 263-278 (2022).
MSC:  92D20 92C15 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Long paths make pattern-counting hard, and deep trees make it Harder. (English) Zbl 07803600

Golovach, Petr A. (ed.) et al., 16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 214, Article 22, 17 p. (2021).
MSC:  68Q25 68Q27 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. (English) Zbl 1490.68151

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, 608-622 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized complexity of two-interval pattern problem. (English) Zbl 07759284

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 16, 10 p. (2020).
MSC:  68Q27 05C62 68R05
PDFBibTeX XMLCite
Full Text: DOI

Fine-grained complexity of regular expression pattern matching and membership. (English) Zbl 07651219

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

The complexity of the approximate multiple pattern matching problem for random strings. (English) Zbl 07651042

Drmota, Michael (ed.) et al., 31st international conference on probabilistic, combinatorial and asymptotic methods for the analysis of algorithms, AofA 2020, Klagenfurt, Austria (virtual conference), June 15–19, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 159, Article 3, 15 p. (2020).
MSC:  68W40
PDFBibTeX XMLCite
Full Text: DOI

Decidability and periodicity of low complexity tilings. (English) Zbl 07650899

Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 14, 12 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Hamming distance completeness. (English) Zbl 07559182

Pisanti, Nadia (ed.) et al., 30th annual symposium on combinatorial pattern matching, CPM 2019, Pisa, Italy, June 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 128, Article 14, 17 p. (2019).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI

The parameterized complexity of finding point sets with hereditary properties. (English) Zbl 1520.68048

Paul, Christophe (ed.) et al., 13th international symposium on parameterized and exact computation, IPEC 2018, August 22–24, 2018, Helsinki, Finland. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 115, Article 11, 14 p. (2019).
MSC:  68Q27 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

State complexity of single-word pattern matching in regular languages. (English) Zbl 1434.68238

Hospodár, Michal (ed.) et al., Descriptional complexity of formal systems. 21st IFIP WG 1.02 international conference, DCFS 2019, Košice, Slovakia, July 17–19, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11612, 86-97 (2019).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI HAL

Brief announcement: Hamming distance completeness and sparse matrix multiplication. (English) Zbl 1499.68145

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 109, 4 p. (2018).
MSC:  68Q25 68W40
PDFBibTeX XMLCite
Full Text: DOI

Tight conditional lower bounds for longest common increasing subsequence. (English) Zbl 1443.68068

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

On matching generalised repetitive patterns. (English) Zbl 1517.68141

Hoshi, Mizuho (ed.) et al., Developments in language theory. 22nd international conference, DLT 2018, Tokyo, Japan, September 10–14, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11088, 269-281 (2018).
MSC:  68Q25 68Q17 68W32
PDFBibTeX XMLCite
Full Text: DOI

Subexponential parameterized algorithms for graphs of polynomial growth. (English) Zbl 1442.68178

Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 59, 15 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Communication and streaming complexity of approximate pattern matching. (English) Zbl 1434.68743

Kärkkäinen, Juha (ed.) et al., 28th annual symposium on combinatorial pattern matching. CPM 2017, Warsaw, Poland, July 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 78, Article 13, 11 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

A walk through combinatorics. An introduction to enumeration and graph theory. With a foreword by Richard Stanley. 4th edition. (English) Zbl 1361.05001

Hackensack, NJ: World Scientific (ISBN 978-981-3148-84-0/hbk). xx, 593 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns. (English) Zbl 1387.68118

Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 652-661 (2016).
MSC:  68Q15 68Q25
PDFBibTeX XMLCite
Full Text: DOI Link

Computing the pattern waiting time: a revisit of the intuitive approach. (English) Zbl 1398.60063

Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 39, 12 p. (2016).
MSC:  60G40 60J10 65Y20
PDFBibTeX XMLCite
Full Text: DOI

Mind the gap: essentially optimal algorithms for online dictionary matching with one gap. (English) Zbl 1398.68207

Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 12, 12 p. (2016).
MSC:  68Q25 68Q17 68W32
PDFBibTeX XMLCite
Full Text: DOI

Streaming pattern matching with \(d\) wildcards. (English) Zbl 1397.68241

Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 44, 16 p. (2016).
MSC:  68W32 68Q25 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

all top 3

Software