On the parameterized complexity of d-dimensional point set pattern matching
| Autor: | Christian Knauer, Sergio Cabello, Panos Giannopoulos |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Discrete mathematics
Matching (graph theory) Computational complexity theory Dimension (graph theory) Parameterized complexity Computational geometry Isometry (Riemannian geometry) Computer Science Applications Theoretical Computer Science Combinatorics Signal Processing Pattern matching Graph isomorphism Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 105:73-77 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2007.08.003 |
| Popis: | Deciding whether two n-point sets A, B ∈ℝ d are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect