Linear-time computability of combinatorial problems on series-parallel graphs

DOI10.1145/322326.322328zbMath0485.68055OpenAlexW2003021478WikidataQ29041672 ScholiaQ29041672MaRDI QIDQ3945592

Nobuji Saito, K. Takamizawa, Takao Nishizeki

Publication date: 1982

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322326.322328

zbMATH Keywords

planar graphsdecision problemseries-parallel graphedge-deletion problemforbidden graphmaximum matching problemminimum vertex cover problemminimum feedback vertex set problemgeneralized matching problemmaximum disjoint triangle problemmaximum line-subgraph problemmaximum outerplanar subgraph problemvertex-deletion problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Quadratic bottleneck knapsack problems, A compact labelling scheme for series-parallel graphs, Arborescence polytopes for series-parallel graphs, Efficient Vertex- and Edge-Coloring of Outerplanar Graphs, A recurrence template for several parameters in series-parallel graphs, Combinatorial algorithms on a class of graphs, Regularity and locality in \(k\)-terminal graphs, On some complexity properties of N-free posets and posets with bounded decomposition diameter, Tree-edges deletion problems with bounded diameter obstruction sets, Maximum independent number for series-parallel networks, Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem, Membrane computing to enhance time efficiency of minimum dominating set, A parallel algorithm for edge-coloring partial k-trees, Minimum Linear Arrangement of Series-Parallel Graphs, Dynamic expression trees, N-free posets as generalizations of series-parallel posets, Parallel recognition and decomposition of two terminal series parallel graphs, Minimum-maximal matching in series-parallel graphs, Practical algorithms on partial k-trees with an application to domination-like problems, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Scheduling UET-UCT series-parallel graphs on two processors, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Linear time algorithms for NP-hard problems restricted to partial k- trees, Optimal location of a path or tree on a network with cycles, Network construction/restoration problems: cycles and complexity, Extensive facility location problems on networks: an updated review, On Strict (Outer-)Confluent Graphs, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, The connected critical node problem, Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time, Packing 2- and 3-stars into cubic graphs, Optimal packet scan against malicious attacks in smart grids, The price of anarchy in series-parallel network congestion games, Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs, The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices, Combinatorial problems on series-parallel graphs, Measuring the distance to series-parallelity by path expressions, Unnamed Item, Unnamed Item, On strict (outer-)confluent graphs, On two dual classes of planar graphs, Recognition of directed acyclic graphs by spanning tree automata, Bandwidth consecutive multicolorings of graphs, On minimum dominating sets with minimum intersection, Practical algorithms for MSO model-checking on tree-decomposable graphs, A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees, Algorithms for recognition of regular properties and decomposition of recursive graph families, The role of Steiner hulls in the solution to Steiner tree problems, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Problems with generalized Steiner problems, THE NUMBER OF LABELED TETRACYCLIC SERIES-PARALLEL BLOCKS, Cross-series-parallel digraphs, Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size, Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs, Monadic second-order evaluations on tree-decomposable graphs, Minimum perfect bipartite matchings and spanning trees under categorization, Parallel recognition of series-parallel graphs, Star Partitions of Perfect Graphs, Small grid drawings of planar graphs with balanced partition, General vertex disjoint paths in series-parallel graphs, Partitioning graphs of supply and demand, A survey of very large-scale neighborhood search techniques, Efficiently parallelizable problems on a class of decomposable graphs, Graph theory (algorithmic, algebraic, and metric problems), Minimum-weight two-connected spanning networks, The edge-disjoint paths problem is NP-complete for series-parallel graphs, Layered graphs: applications and algorithms, Approximability of partitioning graphs with supply and demand, Minimum-cost strong network orientation problems: Classification, complexity, and algorithms, A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs, The Second Riddell Relation and Its Consequences, Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata, On finding a minimum vertex cover of a series-parallel graph, Jump number maximization for proper interval graphs and series-parallel graphs, Analyse de sensibilité pour les problèmes linéaires en variables 0-1, Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks, NodeTrix planarity testing with small clusters, Computing equilibrium in network utility-sharing and discrete election games, A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES, The traveling salesman problem on a graph and some related integer polyhedra, A note on the tour problems in two-terminal series-parallel graphs, Decomposition by clique separators, Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey, A linear-time certifying algorithm for recognizing generalized series-parallel graphs, The quadratic 0-1 knapsack problem with series-parallel support, The Steiner tree polytope and related polyhedra