δγ - 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 条
  • [21] A faster parameterized algorithm for temporal matching
    Zschoche, Philipp
    INFORMATION PROCESSING LETTERS, 2022, 174
  • [22] Parameterized Algorithms and Kernels for Rainbow Matching
    Gupta, Sushmita
    Roy, Sanjukta
    Saurabh, Saket
    Zehavi, Meirav
    ALGORITHMICA, 2019, 81 (04) : 1684 - 1698
  • [23] Parameterized pattern matching: Algorithms and applications
    Baker, BS
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1996, 52 (01) : 28 - 42
  • [24] On the parameterized complexity of the acyclic matching problem
    Hajebi, Sahab
    Javadi, Ramin
    THEORETICAL COMPUTER SCIENCE, 2023, 958
  • [25] Parameterized Algorithms and Kernels for Rainbow Matching
    Sushmita Gupta
    Sanjukta Roy
    Saket Saurabh
    Meirav Zehavi
    Algorithmica, 2019, 81 : 1684 - 1698
  • [26] Parameterized dictionary matching and recognition with one gap
    Shalom, B. Riva
    THEORETICAL COMPUTER SCIENCE, 2021, 854 : 1 - 16
  • [27] Online parameterized dictionary matching with one gap
    Levy, Avivit
    Shalom, B. Riva
    THEORETICAL COMPUTER SCIENCE, 2020, 845 : 208 - 229
  • [28] Parameterized algorithms and kernels for almost induced matching
    Xiao, Mingyu
    Kou, Shaowei
    THEORETICAL COMPUTER SCIENCE, 2020, 846 : 103 - 113
  • [29] Parameterized algorithms for weighted matching and packing problems
    Liu, Yunlong
    Chen, Jianer
    Wang, Jianxin
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2007, 4484 : 692 - +
  • [30] An improved parameterized algorithm for a generalized matching problem
    Wang, Jianxin
    Ning, Dan
    Feng, Qilong
    Chen, Jianer
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2008, 4978 : 212 - 222
12345