A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree (Q1736548)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree |
scientific article |
Statements
A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree (English)
0 references
26 March 2019
0 references
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.
0 references
maximum common subgraph
0 references
outerplanar graph
0 references
dynamic programming
0 references
0 references
0 references
0 references
0 references