دانلود مقاله ترجمه شده ارائه یک الگوریتم با پیچیدگی زمانی چند جمله ای جهت حل مسأله زیرگراف متصل مشترک با بیشترین یال برای گراف های مسطح بیرونی با درجه محدود

Abstract

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

Contents

1. Introduction

2. Preliminaries

3. Algorithm for a Restricted Case

4. Algorithm for Outerplanar Graphs of Bounded Degree

5. Concluding Remarks