A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree

DOI10.1007/978-3-642-32589-2_10zbMath1365.05271OpenAlexW192266888MaRDI QIDQ2912710

Takeyuki Tamura, Tatsuya Akutsu

Publication date: 25 September 2012

Published in: Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32589-2_10

zbMATH Keywords

dynamic programmingouterplanar graphmaximum common subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Automatic Inference of Graph Transformation Rules Using the Cyclic Nature of Chemical Reactions ⋮ On the complexity of submap isomorphism and maximum common submap problems ⋮ A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree ⋮ Unnamed Item

This page was built for publication: A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree