Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time

DOI10.1137/S0097539794275872MaRDI QIDQ4943755zbMATH OpenOpenAlexFDO

Authors Juha Kärkkäinen, Esko Ukkonen

Publication date 19 March 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794275872

zbMATH Keywords

approximate matchingaverage case analysismultidimensional matching

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1003305
• Approximation algorithms for maximum two-dimensional pattern matching
• Two-dimensional pattern matching in linear time and small space
• A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching
• On the computational complexity of 2-interval pattern matching problems
• Fast algorithms for two dimensional and multiple pattern matching
• On linear-time alphabet-independent 2-dimensional pattern matching

Cited in

(19)

• Analysis of two-dimensional approximate pattern matching algorithms
• On the computational complexity of 2-interval pattern matching problems
• Multiple matching of rectangular patterns
• Sequential and indexed two-dimensional combinatorial template matching allowing rotations
• scientific article; zbMATH DE number 1003305 (Why is no real title available?)
• Efficient randomized pattern-matching algorithms
• scientific article; zbMATH DE number 4126689 (Why is no real title available?)
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Two-dimensional pattern matching in linear time and small space
• Pattern Matching with Variables: A Multivariate Complexity Analysis
• Fast algorithms for two dimensional and multiple pattern matching
• Template-based pattern matching in two-dimensional arrays
• On linear-time alphabet-independent 2-dimensional pattern matching
• Quantum pattern matching fast on average
• Approximation algorithms for maximum two-dimensional pattern matching
• Two-dimensional pattern matching by sampling
• Optimal bounds for distinct quartics
• The four corners problem over larger alphabets
• Pattern matching in doubling spaces

This page was built for publication: Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time

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