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:
“The great question that has never been answered, and which I have not yet been able to answer, despite my thirty years of research into the feminine soul, is “What does a woman want?” [Was will das Weib?]”
—Sigmund Freud (1856–1939)
“Living is like working out a long addition sum, and if you make a mistake in the first two totals you will never find the right answer. It means involving oneself in a complicated chain of circumstances.”
—Cesare Pavese (1908–1950)