Journal
EUROPEAN JOURNAL OF COMBINATORICS
Volume 68, Issue -, Pages 79-95Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.ejc.2017.07.012
Keywords
-
Categories
Funding
- German Research Foundation (DFG), priority program Algorithms for Big Data [SPP 1736]
Ask authors/readers for more resources
The complexity of the maximum common connected subgraph problem in partial k-trees is still not fully understood. Polynomial time solutions are known for degree-bounded outerplanar graphs, a subclass of the partial 2-trees. On the other hand, the problem is known to be NP-hard in vertex-labeled partial 11-trees of bounded degree. We consider series-parallel graphs, i.e., partial 2-trees. We show that the problem remains NP-hard in biconnected series-parallel graphs with all but one vertex of degree 3 or less. A positive complexity result is presented for a related problem of high practical relevance which asks for a maximum common connected subgraph that preserves blocks and bridges of the input graphs. We present a polynomial time algorithm for this problem in series parallel graphs, which utilizes a combination of BC- and SP-tree data structures to decompose both graphs. (C) 2017 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available