On the complexity of submap isomorphism and maximum common submap problems

DOI10.1016/j.patcog.2014.05.019zbMath1373.68355OpenAlexW2164952701WikidataQ115926514 ScholiaQ115926514MaRDI QIDQ1677051

Colin de la Higuera, Jean-Christophe Janodet, Christine Solnon, Guillaume Damiand

Publication date: 10 November 2017

Published in: Pattern Recognition (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.patcog.2014.05.019

zbMATH Keywords

complexityplane graphgeneralized mapfixed-parameter tractable (FPT)maximum common submapsubmap isomorphism

Mathematics Subject Classification ID

Applications of graph theory (05C90) Pattern recognition, speech recognition (68T10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Preface of special issue on ``Graph-based processing for pattern recognition ⋮ Arbitrary Overlap Constraints in Graph Packing Problems ⋮ Unnamed Item ⋮ Constraints for symmetry breaking in graph representation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• AllDifferent-based filtering for subgraph isomorphism
• A parametric filtering algorithm for the graph isomorphism problem
• The subgraph isomorphism problem for outerplanar graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Enumerating all connected maximal common subgraphs in two graphs
• A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
• A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree
• Measuring the Distance of Generalized Maps
• Planar Subgraph Isomorphism Revisited
• A Polynomial Algorithm for Submap Isomorphism
• Efficient Suboptimal Graph Isomorphism
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Subtree Isomorphism in O(n5/2)
• A graph distance metric based on the maximal common subgraph
• N-DIMENSIONAL GENERALIZED COMBINATORIAL MAPS AND CELLULAR QUASI-MANIFOLDS
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Adjacency in digital pictures
• On the Complexity of Submap Isomorphism

This page was built for publication: On the complexity of submap isomorphism and maximum common submap problems