Topology of series-parallel networks

DOI10.1016/0022-247X(65)90125-3zbMath0128.37002OpenAlexW2073840571WikidataQ100604477 ScholiaQ100604477MaRDI QIDQ2394739

Richard J. Duffin

Publication date: 1965

Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-247x(65)90125-3

zbMATH Keywords

numerical analysis

Related Items (only showing first 100 items - show all)

A graphical representation of relational formulae with complementation ⋮ Describing the local structure of sequence graphs ⋮ A tight relation between series-parallel graphs and bipartite distance hereditary graphs ⋮ LIST POINT ARBORICITY OF GRAPHS ⋮ On the Uniqueness of Equilibrium in Atomic Splittable Routing Games ⋮ Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs ⋮ A homogenization result for planar, polygonal networks ⋮ On group choosability of total graphs ⋮ An Analytic Propositional Proof System on Graphs ⋮ The Merino-Welsh conjecture holds for series-parallel graphs ⋮ Lehman's Theorem and the Directed Steiner Tree Problem ⋮ Colouring series-parallel graphs ⋮ Characterization and Recognition of Partial 3-Trees ⋮ Searching for an intruder on graphs and their subdivisions ⋮ Collusion in atomic splittable routing games ⋮ On lengths of edge-labeled graph expressions ⋮ Edge-group choosability of outerplanar and near-outerplanar graphs ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ On Strict (Outer-)Confluent Graphs ⋮ Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings ⋮ Resolving Braess's paradox in random networks ⋮ Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs ⋮ Strong chromatic index of \(K_4\)-minor free graphs ⋮ Estimation of expressions' complexities for two-terminal directed acyclic graphs ⋮ Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs ⋮ Chronological rectangle digraphs which are two-terminal series-parallel ⋮ List star edge-coloring of \(k\)-degenerate graphs and \(K_4\)-minor free graphs ⋮ Confluence up to Garbage ⋮ Trader multiflow and box-TDI systems in series-parallel graphs ⋮ Toughness and spanning trees in K4‐minor‐free graphs ⋮ Market equilibrium in multi‐tier supply chain networks ⋮ Motives of melonic graphs ⋮ A note on social learning in non-atomic routing games ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Strict neighbor-distinguishing index of \(K_4\)-minor-free graphs ⋮ Capacity-preserving subgraphs of directed flow networks ⋮ Measuring the distance to series-parallelity by path expressions ⋮ Box-total dual integrality and edge-connectivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exact Learning of Finite Unions of Graph Patterns from Queries ⋮ Unnamed Item ⋮ The st-bond polytope on series-parallel graphs ⋮ Graph theory in Coq: minors, treewidth, and isomorphisms ⋮ Substitutes and Complements in Constrained Linear Models ⋮ Graphs with no 7-wheel subdivision ⋮ Network Resilience ⋮ A Combinatorial Model for Series-Parallel Networks ⋮ Equistable distance-hereditary graphs ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ A new graph parameter related to bounded rank positive semidefinite matrix completions ⋮ Series-parallel graphs are windy postman perfect ⋮ Growth Rates and Critical Exponents of Classes of Binary Combinatorial Geometries ⋮ Distance Hereditary Graphs and the Interlace Polynomial ⋮ Algorithms for core stability, core largeness, exactness, and extendability of flow games ⋮ The determination of the total chromatic number of series-parallel graphs with \((G) \geq 4\) ⋮ On the dominant of the Steiner 2-edge connected subgraph polytope ⋮ Steiner trees and polyhedra ⋮ Determinacy in Linear Systems and Networks ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ Normal forms for binary relations ⋮ Complexity of finding a join of maximum weight ⋮ Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability ⋮ Minimum-cost strong network orientation problems: Classification, complexity, and algorithms ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Informational Braess’ Paradox: The Effect of Information on Traffic Congestion ⋮ Analyse de sensibilité pour les problèmes linéaires en variables 0-1 ⋮ Hadwiger’s Conjecture ⋮ Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks ⋮ Weak Unit Disk and Interval Representation of Graphs ⋮ Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited ⋮ \(k\)-edge connected polyhedra on series-parallel graphs ⋮ Applications of matroids in electric network theory ⋮ Coloring Cubic Graphs by Point-Intransitive Steiner Triple Systems ⋮ The Concept of Two-Chord Tiesets and Its Application to an Algebraic Characterization of Non-Series-Parallel Graphs ⋮ Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph ⋮ The entire coloring of series-parallel graphs ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2 ⋮ The \(r\)-acyclic chromatic number of planar graphs ⋮ A linear-time certifying algorithm for recognizing generalized series-parallel graphs ⋮ Nested Graphs ⋮ \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method ⋮ Denotational fixed-point semantics for constructive scheduling of synchronous concurrency ⋮ Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs ⋮ Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs ⋮ Perfect edge domination and efficient edge domination in graphs ⋮ A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs ⋮ A compact labelling scheme for series-parallel graphs ⋮ A solvable case of quadratic 0-1 programming ⋮ Arborescence polytopes for series-parallel graphs ⋮ Two-edge connected spanning subgraphs and polyhedra ⋮ Approximating the distribution functions in stochastic networks ⋮ Combinatorial algorithms on a class of graphs ⋮ On some complexity properties of N-free posets and posets with bounded decomposition diameter ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Multiterminal duality and three-terminal series-parallelness ⋮ Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron

Cites Work

• Unnamed Item
• Non-linear network problems
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Nonlinear networks. IIa
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: Topology of series-parallel networks