A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree
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 t...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2013-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/6/1/119 |
| _version_ | 1811335451869446144 |
|---|---|
| author | Takeyuki Tamura Tatsuya Akutsu |
| author_facet | Takeyuki Tamura Tatsuya Akutsu |
| author_sort | Takeyuki Tamura |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-13T17:24:26Z |
| format | Article |
| id | doaj.art-b13e9f4f4c4a4da78cac2ef980084617 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-13T17:24:26Z |
| publishDate | 2013-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-b13e9f4f4c4a4da78cac2ef9800846172022-12-22T02:37:51ZengMDPI AGAlgorithms1999-48932013-02-016111913510.3390/a6010119A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded DegreeTakeyuki TamuraTatsuya AkutsuThe 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.http://www.mdpi.com/1999-4893/6/1/119maximum common subgraphouterplanar graphdynamic programming |
| spellingShingle | Takeyuki Tamura Tatsuya Akutsu A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree Algorithms maximum common subgraph outerplanar graph dynamic programming |
| title | A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree |
| title_full | A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree |
| title_fullStr | A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree |
| title_full_unstemmed | A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree |
| title_short | A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree |
| title_sort | polynomial time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree |
| topic | maximum common subgraph outerplanar graph dynamic programming |
| url | http://www.mdpi.com/1999-4893/6/1/119 |
| work_keys_str_mv | AT takeyukitamura apolynomialtimealgorithmforcomputingthemaximumcommonconnectededgesubgraphofouterplanargraphsofboundeddegree AT tatsuyaakutsu apolynomialtimealgorithmforcomputingthemaximumcommonconnectededgesubgraphofouterplanargraphsofboundeddegree AT takeyukitamura polynomialtimealgorithmforcomputingthemaximumcommonconnectededgesubgraphofouterplanargraphsofboundeddegree AT tatsuyaakutsu polynomialtimealgorithmforcomputingthemaximumcommonconnectededgesubgraphofouterplanargraphsofboundeddegree |