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 (87)

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 ⋮ Finding edge-disjoint paths in partial k-trees ⋮ 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

This page was built for publication: Linear-time computability of combinatorial problems on series-parallel graphs