Research Involving Series-parallel Graphs
SPGs may be recognized in linear time and their series-parallel decomposition may be constructed in linear time as well.
Besides being a model of certain types of electric networks, these graphs are of interest in computational complexity theory, because a number of standard graph problems are solvable in linear time on SPGs, including finding of the maximum matching, maximum independent set, minimum dominating set and Hamiltonian completion. Some of these problems are NP-complete for general graphs. The solution capitalizes on the fact that if the answers for one of these problems are known for two SP-graphs, then one can quickly find the answer for their series and parallel compositions.
The series-parallel networks problem refers to a graph enumeration problem which asks for the number of series-parallel graphs that can be formed using a given number of edges.
Read more about this topic: Series-parallel Graph
Famous quotes containing the words research and/or involving:
“One of the most important findings to come out of our research is that being where you want to be is good for you. We found a very strong correlation between preferring the role you are in and well-being. The homemaker who is at home because she likes that “job,” because it meets her own desires and needs, tends to feel good about her life. The woman at work who wants to be there also rates high in well-being.”
—Grace Baruch (20th century)
“The problem, thus, is not whether or not women are to combine marriage and motherhood with work or career but how they are to do so—concomitantly in a two-role continuous pattern or sequentially in a pattern involving job or career discontinuities.”
—Jessie Bernard (20th century)