A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
type: Item
instance of: scholarly article
title: A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
zbMATH Open document ID: 1461.68140
author: Tatsuya Akutsu
author: Takeyuki Tamura
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: The maximum common connected edge subgraph problem is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs, where it has applications in pattern recognition and chemistry. This paper presents a dynamic programming algorithm for the problem when the two input graphs are outerplanar graphs of a bounded vertex degree, where it is known that the problem is NP-hard, even for outerplanar graphs of an unbounded degree. Although the algorithm repeatedly modifies input graphs, it is shown that the number of relevant subproblems is polynomially bounded, and thus, the algorithm works in polynomial time.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7042154
zbMATH Keywords: maximum common subgraph
zbMATH Keywords: outerplanar graph
zbMATH Keywords: dynamic programming
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6010119
OpenAlex ID: W2046820662
Wikidata QID: Q115926164
cites work: Video indexing and similarity retrieval by largest common subgraph detection using decision trees
cites work: On the approximability of the maximum common subgraph problem
cites work: Q4198056
cites work: Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
cites work: A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
cites work: Computing and Drawing Isomorphic Subgraphs
cites work: Subgraph isomorphism for biconnected outerplanar graphs in cubic time
cites work: The subgraph isomorphism problem for outerplanar graphs
cites work: Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
cites work: Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
cites work: A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree
cites work: Characterizations of outerplanar graphs
cites work: Q3451017
cites work: Q3651735
cites work: On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree
DOI: 10.3390/A6010119
description: scientific article; zbMATH DE number 7042154