Linear-time computability of combinatorial problems on series-parallel graphs
From MaRDI portal
Publication:3945592
decision problemedge-deletion problemforbidden graphgeneralized matching problemmaximum disjoint triangle problemmaximum line-subgraph problemmaximum matching problemmaximum outerplanar subgraph problemminimum feedback vertex set problemminimum vertex cover problemplanar graphsseries-parallel graphvertex-deletion problem
Cited in
(92)- Approximability of partitioning graphs with supply and demand
- Decomposition by clique separators
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- A compact labelling scheme for series-parallel graphs
- On some complexity properties of N-free posets and posets with bounded decomposition diameter
- 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
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Combinatorial problems on series-parallel graphs
- On minimum dominating sets with minimum intersection
- 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
- Minimum perfect bipartite matchings and spanning trees under categorization
- Parallel recognition of series-parallel graphs
- General vertex disjoint paths in series-parallel graphs
- A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs
- A note on the tour problems in two-terminal series-parallel graphs
- The Steiner tree polytope and related polyhedra
- Arborescence polytopes for series-parallel 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
- Dynamic expression trees
- Scheduling UET-UCT series-parallel graphs on two processors
- Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
- Extensive facility location problems on networks: an updated review
- Efficiently parallelizable problems on a class of decomposable graphs
- Jump number maximization for proper interval graphs and series-parallel graphs
- The quadratic 0-1 knapsack problem with series-parallel support
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Recognition of directed acyclic graphs by spanning tree automata
- Cross-series-parallel digraphs
- Computing equilibrium in network utility-sharing and discrete election games
- A linear-time certifying algorithm for recognizing generalized series-parallel graphs
- Network construction/restoration problems: cycles and complexity
- On strict (outer-)confluent graphs
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- Layered graphs: applications and algorithms
- Quadratic bottleneck knapsack problems
- Tree-edges deletion problems with bounded diameter obstruction sets
- Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
- Bandwidth consecutive multicolorings of graphs
- Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size
- Membrane computing to enhance time efficiency of minimum dominating set
- The connected critical node problem
- Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks
- Optimal location of a path or tree on a network with cycles
- Minimum Linear Arrangement of Series-Parallel Graphs
- Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata
- The traveling salesman problem on a graph and some related integer polyhedra
- Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
- Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
- Maximum independent number for series-parallel networks
- Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- The second Riddell relation and its consequences
- scientific article; zbMATH DE number 7378361 (Why is no real title available?)
- A parallel algorithm for edge-coloring partial k-trees
- Practical algorithms on partial k-trees with an application to domination-like problems
- On strict (outer-)confluent graphs
- The number of labeled tetracyclic series-parallel blocks
- A polynomial-time algorithm for finding total colorings of partial \(k\)-trees
- Analyse de sensibilité pour les problèmes linéaires en variables 0-1
- Graph theory (algorithmic, algebraic, and metric problems)
- Minimum-weight two-connected spanning networks
- scientific article; zbMATH DE number 7656033 (Why is no real title available?)
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time
- Packing 2- and 3-stars into cubic graphs
- The price of anarchy in series-parallel network congestion games
- The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
- Measuring the distance to series-parallelity by path expressions
- Finding edge-disjoint paths in partial k-trees
- Definability equals recognizability of partial 3-trees
- A (1/2+1/60)-approximation algorithm for maximum weight series-parallel subgraph
- Design of survivable networks with low connectivity requirements
- Monadic second-order evaluations on tree-decomposable graphs
- Small grid drawings of planar graphs with balanced partition
- A survey of very large-scale neighborhood search techniques
- On one approach to enumeration of labeled connected graphs: a review
- Pipe merging for transient gas network optimization problems
- Graph polynomials and local graph operations
- Perfect hierarchical matchings in graphs
- On finding a minimum vertex cover of a series-parallel graph
- Optimal packet scan against malicious attacks in smart grids
- Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
- On two dual classes of planar graphs
- Partitioning graphs of supply and demand
This page was built for publication: Linear-time computability of combinatorial problems on series-parallel graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3945592)
