Polynomial algorithms for open plane graph and subgraph isomorphisms

DOI10.1016/J.TCS.2013.05.026MaRDI QIDQ391207zbMATH OpenOpenAlexDBLPWikidataFDO

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

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

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

Recommendations

• A Polynomial Algorithm for Submap Isomorphism
• Subgraph Isomorphism in Planar Graphs and Related Problems
• scientific article; zbMATH DE number 4114685
• Isomorphism of planar graphs (working paper)
• On the complexity of submap isomorphism

Cites work

• scientific article; zbMATH DE number 2123122 (Why is no real title available?)
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 3489159 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• A Polynomial Algorithm for Submap Isomorphism
• A large database of graphs and its use for benchmarking graph isomorphism algorithms
• A parametric filtering algorithm for the graph isomorphism problem
• Filtering for Subgraph Isomorphism
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• N-DIMENSIONAL GENERALIZED COMBINATORIAL MAPS AND CELLULAR QUASI-MANIFOLDS
• Planar subgraph isomorphism revisited
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The minimum broadcast time problem for several processor networks

Cited in

(5)

• Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
• The SVE method for regular graph isomorphism identification
• On the complexity of submap isomorphism
• Computing the overlaps of two maps
• A Polynomial Algorithm for Submap Isomorphism

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

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