Polynomial algorithms for open plane graph and subgraph isomorphisms

DOI10.1016/j.tcs.2013.05.026zbMath1301.05344DBLPjournals/tcs/HigueraJSDS13OpenAlexW2098398499WikidataQ56270747 ScholiaQ56270747MaRDI QIDQ391207

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

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.05.026

zbMATH Keywords

NP-complete problemsequivalence and isomorphismopen plane graphspolynomial problemssubgraphs and patterns

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

The SVE method for regular graph isomorphism identification ⋮ Computing the Overlaps of Two Maps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The minimum broadcast time problem for several processor networks
• A parametric filtering algorithm for the graph isomorphism problem
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• Planar Subgraph Isomorphism Revisited
• Filtering for Subgraph Isomorphism
• A Polynomial Algorithm for Submap Isomorphism
• N-DIMENSIONAL GENERALIZED COMBINATORIAL MAPS AND CELLULAR QUASI-MANIFOLDS
• A large database of graphs and its use for benchmarking graph isomorphism algorithms
• Subgraph Isomorphism in Planar Graphs and Related Problems

This page was built for publication: Polynomial algorithms for open plane graph and subgraph isomorphisms