Back to Search
Start Over
A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree
- Source :
- Algorithms, Vol 6, Iss 1, Pp 119-135 (2013), Algorithms, Volume 6, Issue 1, Pages 119-135
- Publication Year :
- 2013
- Publisher :
- MDPI AG, 2013.
-
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.
- Subjects :
- dynamic programming
Discrete mathematics
Numerical Analysis
lcsh:T55.4-60.8
maximum common subgraph
Subgraph isomorphism problem
1-planar graph
lcsh:QA75.5-76.95
Theoretical Computer Science
outerplanar graph
Combinatorics
Computational Mathematics
Indifference graph
Pathwidth
Computational Theory and Mathematics
Computer Science::Discrete Mathematics
Chordal graph
Partial k-tree
lcsh:Industrial engineering. Management engineering
Induced subgraph isomorphism problem
Cograph
lcsh:Electronic computers. Computer science
Algorithm
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- ISSN :
- 19994893
- Volume :
- 6
- Database :
- OpenAIRE
- Journal :
- Algorithms
- Accession number :
- edsair.doi.dedup.....af9acf9f677bbe3b79306d4da88db3cc