[go: up one dir, main page]

Ouangraoua et al., 2009 - Google Patents

A constrained edit distance algorithm between semi-ordered trees

Ouangraoua et al., 2009

View PDF
Document ID
15118096006898851160
Author
Ouangraoua A
Ferraro P
Publication year
Publication venue
Theoretical computer science

External Links

Snippet

In this paper, we propose a formal definition of a new class of trees called semi-ordered trees and a polynomial dynamic programming algorithm to compute a constrained edit distance between such trees. The core of the method relies on a similar approach to …
Continue reading at www.sciencedirect.com (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/22—Manipulating or registering by use of codes, e.g. in sequence of text characters
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06K—RECOGNITION OF DATA; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
    • G06K9/00—Methods or arrangements for reading or recognising printed or written characters or for recognising patterns, e.g. fingerprints
    • G06K9/62—Methods or arrangements for recognition using electronic means
    • G06K9/6267—Classification techniques
    • G06K9/6279—Classification techniques relating to the number of classes
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees

Similar Documents

Publication Publication Date Title
Frellesvig et al. Vector space of Feynman integrals and multivariate intersection numbers
Cole et al. An O (n log n) algorithm for the maximum agreement subtree problem for binary trees
Hellmuth et al. Orthology relations, symbolic ultrametrics, and cographs
Bille A survey on tree edit distance and related problems
Baswana et al. Dynamic DFS in undirected graphs: Breaking the o(m) barrier
Sidorov et al. Computing text similarity using tree edit distance
Bryant et al. Computing the quartet distance between evolutionary trees
He et al. A study of Feynman integrals with uniform transcendental weights and their symbology
Wetzels et al. Branch Decomposition‐Independent Edit Distances for Merge Trees
Ouangraoua et al. A constrained edit distance algorithm between semi-ordered trees
Brodal et al. Computing the quartet distance between evolutionary trees in time O (n log2 n)
Jansson et al. A fast algorithm for optimal alignment between similar ordered trees
Wang et al. Parametric alignment of ordered trees
Lee et al. An improved algorithm for the maximum agreement subtree problem
Gosselin et al. Efficient search of combinatorial maps using signatures
He et al. IPEDX: An exact algorithm for pedigree reconstruction using genotype data
Bryant et al. Supertree methods for ancestral divergence dates and other applications
Jansson et al. A fast algorithm for optimal alignment between similar ordered trees
Christiansen et al. Computing the quartet distance between trees of arbitrary degree
Haas Solving large-scale minimum-weight triangulation instances to provable optimality
Akutsu et al. A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
Köbler et al. Interval graphs: Canonical representation in logspace
Chen et al. Parameterized and approximation algorithms for the MAF problem in multifurcating trees
Feng et al. On the variety of shapes on the fringe of a random recursive tree
Hsu A linear time algorithm for finding a maximal planar subgraph based on PC-trees