2013年
A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded Degree
Algorithms
- ,
- 巻
- 6
- 号
- 1
- 開始ページ
- 119
- 終了ページ
- 135
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.3390/a6010119
- 出版者・発行元
- MDPI AG
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. © 2013 by the authors.
- リンク情報
-
- DOI
- https://doi.org/10.3390/a6010119
- DBLP
- https://dblp.uni-trier.de/rec/journals/algorithms/AkutsuT13
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201502813750847242
- CiNii Articles
- http://ci.nii.ac.jp/naid/120005243648
- URL
- http://dblp.uni-trier.de/db/journals/algorithms/algorithms6.html#journals/algorithms/AkutsuT13
- ID情報
-
- DOI : 10.3390/a6010119
- ISSN : 1999-4893
- DBLP ID : journals/algorithms/AkutsuT13
- J-Global ID : 201502813750847242
- CiNii Articles ID : 120005243648
- SCOPUS ID : 84884337673