1982/07/01 by K. Takamizawa, Takao Nishizeki, Naobumi Saito · 3 citations
Computer Science · Engineering · Medicine · #Computability, Logic, AI Algorithms #Algorithms and Data Compression #graph theory and CDMA systems #Computability #Citation #Computer science #Sendai virus #Telecommunications #Library science #Algorithm #Medicine
paper · pdf · doi:10.1145/322326.322328
openalex publication_date 1982/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
A series-parallel graph can be constructed from a certain graph by recurslvely applying "series" and "parallel" connections The class of such graphs, which Is a well-known model of series-parallel electrical networks, is a subclass of planar graphs It is shown in a umfied manner that there exist hnearume algorithms for many combinatorial problems ff an input graph is restricted to the class of series-parallel graphs. These include 0) the decision problem with respect to a property characterized by a finite number of forbidden graphs, (u) the mlmmum edge (vertex) deletion problem with respect to the same property as above, and (Ul) the generalized matching problem Consequently, the following problems, among others, prove to be hnear-tlme computable for the class of series-parallel graphs. (I) the minimum vertex cover problem, (2) the maximum outerplanar (reduced) subgraph problem, (3) the minimum feedback vertex set problem, (4) the maximum (induced) hne-subgraph problem, (5) the maximum matching problem, and (6) the maximum disjoint triangle problem.