Academic Journals Database
Disseminating quality controlled scientific knowledge

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

Author(s): Tatsuya Akutsu | Takeyuki Tamura

Journal: Algorithms
ISSN 1999-4893

Volume: 6;
Issue: 1;
Start page: 119;
Date: 2013;
Original page

Keywords: maximum common subgraph | outerplanar graph | dynamic programming

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.
RPA Switzerland

RPA Switzerland

Robotic process automation


Tango Jona
Tangokurs Rapperswil-Jona