scientific article; zbMATH DE number 6678937

DOI10.4230/LIPICS.STACS.2013.400MaRDI QIDQ2957901zbMATH OpenFDO

Authors Markus Jalsenius, Benny Porat, Benjamin Sach

Publication date 30 January 2017

Full work available at URL https://arxiv.org/abs/1109.5269

zbMATH Keywords

pattern matchingrandomized algorithmsstreaming algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Recommendations

• Better bounds for matchings in the streaming model
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Bipartite matching in the semi-streaming model
• Approximate Maximum Matching in Random Streams
• Maximum matching in semi-streaming with few passes
• The streaming \(k\)-mismatch problem
• Weighted matching in the semi-streaming model
• Weighted matching in the semi-streaming model
• Algorithms – ESA 2004

Cited in

(11)

• Streaming pattern matching with \(d\) wildcards
• A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
• A brief history of parameterized matching problems
• Tight tradeoffs for real-time approximation of longest palindromes in streams
• Pattern matching in multiple streams
• Dictionary matching in a stream
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Approximate Maximum Matching in Random Streams
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Efficient parameterized pattern matching in sublinear space

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957901)