δγ - Parameterized Matching

被引：0

作者：

Lee, Inbok ^{[1
]}

Mendivelso, Juan ^{[2
]}

Pinzon, Yoan J. ^{[2
]}

机构：

[1] Hankuk Aviat Univ, Sch Elect Telecommun & Comp Engn, Koyang City, Kyonggi Do, South Korea

[2] Univ Nacl Colombia, Dept Syst & Ind Engn, Res Grp Algorithms & Combinatorics ALGOS UN, Bogota, Colombia

来源：

STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS | 2008年 / 5280卷

关键词：

combinatorial algorithms; delta-matching; delta gamma-matching; parameterized matching; bipartite matching;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper defines a new pattern matching problem by combining two paradigms: delta gamma-matching and parameterized matching. The solution is essentially obtained by a combination of bitparallel techniques and a reductions to a graph matching problem. The time complexity of the algorithm is O(nm), assuming text size n, pattern size m and a constant size alphabet.

引用

页码：236 / +

页数：4

共 50 条

[31] Parameterized matching on non-linear structures
Amir, Amihood
Navarro, Gonzalo
INFORMATION PROCESSING LETTERS, 2009, 109 (15) : 864 - 867
[32] Parameterized algorithms for weighted matching and packing problems
Wang, Jianxin
Liu, Yunlong
DISCRETE OPTIMIZATION, 2008, 5 (04) : 748 - 754
[33] MATCHING PARAMETERIZED SHAPES BY NONPARAMETRIC BELIEF PROPAGATION
Dong, Xiao
Zheng, Guoyan
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2009, 23 (02) : 209 - 246
[34] Fast parameterized matching with q-grams
Salmela, Leena
Tarhio, Jorma
JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (03) : 408 - 419
[35] PMRF: Parameterized Matching-Ranking Framework
Gmati, Fatma Ezzahra
Yacoubi-Ayadi, Nadia
Bahri, Afef
Chakhar, Salem
Ishizaka, Alessio
SOFTWARE ENGINEERING RESEARCH, MANAGEMENT AND APPLICATIONS, 2016, 654 : 181 - 198
[36] Solving Graph Isomorphism Using Parameterized Matching
Mendivelso, Juan
Kim, Sunghwan
Elnikety, Sameh
He, Yuxiong
Hwang, Seung-won
Pinzon, Yoan
STRING PROCESSING AND INFORMATION RETRIEVAL (SPIRE 2013), 2013, 8214 : 230 - 242
[37] Efficient Parameterized Pattern Matching in Sublinear Space
Ideguchi, Haruki
Hendrian, Diptarama
Yoshinaka, Ryo
Shinohara, Ayumi
STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2023, 2023, 14240 : 271 - 283
[38] A Parameterized Study of Maximum Generalized Pattern Matching Problems
Ordyniak, Sebastian
Popa, Alexandru
ALGORITHMICA, 2016, 75 (01) : 1 - 26
[39] Structure-based models parameterized by fluctuation matching
Lu, Lanyuan
Xia, Fei
Tong, Dudu
ABSTRACTS OF PAPERS OF THE AMERICAN CHEMICAL SOCIETY, 2013, 246
[40] The deterministic pattern matching based on the parameterized quantum circuit
Liu, Lu
Wu, Xing-Yu
Xu, Chu-Yao
Zhang, Lu-Fan
Wang, Chuan
EPJ QUANTUM TECHNOLOGY, 2024, 11 (01)

← 1 2 3 4 5 →