The parameterized complexity of geometric graph isomorphism

DOI10.1007/S00453-015-0024-8MaRDI QIDQ309786zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Gaurav Rattan

Publication date 7 September 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-0024-8

zbMATH Keywords

latticesgraph isomorphismpoint set congruence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• The parameterized complexity of geometric graph isomorphism
• On the geometric graph isomorphism problem
• On the parameterized complexity of \(d\)-dimensional point set pattern matching
• On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching
• scientific article; zbMATH DE number 1555919

Cites work

• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• Congruence, similarity, and symmetries of geometric objects
• Hypergraph isomorphism and structural equivalence of Boolean functions
• On determining the congruence of point sets in \(d\) dimensions
• On the geometric graph isomorphism problem
• On the lattice isomorphism problem
• TESTING THE CONGRUENCE OF d-DIMENSIONAL POINT SETS
• The complexity of low-distortion embeddings between point sets

Cited in

(4)

• On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching
• On the parameterized complexity of \(d\)-dimensional point set pattern matching
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• The parameterized complexity of geometric graph isomorphism

This page was built for publication: The parameterized complexity of geometric graph isomorphism

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