The Recognition of Series Parallel Digraphs

From MaRDI portal
Publication:3936212

DOI10.1137/0211023zbMath0478.68065OpenAlexW1985495277WikidataQ29031100 ScholiaQ29031100MaRDI QIDQ3936212

Jacobo Valdes, Eugene L. Lawler, Robert Endre Tarjan

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0211023



Related Items

Perfect edge domination and efficient edge domination in graphs, A compact labelling scheme for series-parallel graphs, Budget-constrained minimum cost flows, A \(k\)-structure generalization of the theory of 2-structures, A recurrence template for several parameters in series-parallel graphs, Combinatorial algorithms on a class of graphs, Acyclic coloring parameterized by directed clique-width, A polynomial time algorithm to compute the connected treewidth of a series-parallel graph, Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks, Computational aspects of the 2-dimension of partially ordered sets, Constructing maximal slicings from geometry, Greedy concepts for network flow problems, Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation, Linkless symmetric drawings of series parallel digraphs, The three-machine flow-shop problem with arbitrary precedence relations, Computation of equilibria and the price of anarchy in bottleneck congestion games, On finding the jump number of a partial order by substitution decomposition, Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem, A linear algorithm to decompose inheritance graphs into modules, Dynamic expression trees, Exact algorithms for single-machine scheduling with time windows and precedence constraints, A new approach to solving three combinatorial enumeration problems on planar graphs, An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures, Two equational theories of partial words, An efficient parallel algorithm for shortest paths in planar layered digraphs, Estimation of flows in flow networks, Adamant digraphs, Scheduling UET-UCT series-parallel graphs on two processors, The equational theory of pomsets, Functions computed by monotone Boolean formulas with no repeated variables, Series parallel digraphs with loops, The obstructions of a minor-closed set of graphs defined by a context-free grammar, Concurrency and atomicity, Axiomatizing shuffle and concatenation in languages, The discrete time-cost tradeoff problem revisited, Lower bounds for the quadratic semi-assignment problem, Activity nets: A guided tour through some recent developments, On-line algorithms for orders, Parallel \(N\)-free order recognition, Scheduling modular projects on a bottleneck resource, Scheduling series-parallel task graphs to minimize peak memory, Sequencing with general precedence constraints, Exact counting of Euler tours for generalized series-parallel graphs, Criticality analysis of activity networks under interval uncertainty, Single machine scheduling with a generalized job-dependent cumulative effect, On graphs with no induced subdivision of \(K_4\), Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs, Asymptotic enumeration of N-free partial orders, On the complexity of dynamic programming for sequencing problems with precedence constraints, The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability, Transitive closure for restricted classes of partial orders, A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs, Free shuffle algebras in language varieties, Characterization and complexity of uniformly nonprimitive labeled 2-structures, Web services composition: complexity and models, Parallel interval order recognition and construction of interval representations, Budgeted colored matching problems, Network characterizations for excluding Braess's paradox, Monadic second-order evaluations on tree-decomposable graphs, The most vital edges with respect to the number of spanning trees in two- terminal series-parallel graphs, On the calculation of transitive reduction-closure of orders, A two-machine flowshop problem with processing time-dependent buffer constraints-an application in multimedia presentations, Parallel recognition of series-parallel graphs, Sex-equal stable matchings: complexity and exact algorithms, Series-parallel languages on scattered and countable posets, Acyclically 3-colorable planar graphs, The project scheduling problem with production and consumption of resources: a list-scheduling based algorithm, Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure, Efficiently parallelizable problems on a class of decomposable graphs, Scheduling linearly shortening jobs under precedence constraints, Series parallel linkages, On the approximability of minmax (regret) network optimization problems, Project scheduling with irregular costs: complexity, approximability, and algorithms, Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree, A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem, Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors, Aggregation approach for the minimum binary cost tension problem, Scheduling unitary task systems with zero--one communication delays for quasi-interval orders, Series-parallel posets and the Tutte polynomial, On finding a minimum vertex cover of a series-parallel graph, Jump number maximization for proper interval graphs and series-parallel graphs, On the two-dimensional orthogonal drawing of series-parallel graphs, Antichain cutsets, Series-parallel languages and the bounded-width property, A new characterization of \(\mathcal{V} \)-posets, Drawing series parallel digraphs symmetrically, Modular decomposition and transitive orientation, On the complexity of partitioning graphs into connected subgraphs, Optimal scheduling on parallel machines for a new order class, Predicting nearly as well as the best pruning of a planar decision graph., Reduction algorithms for graphs of small treewidth, Rationality in algebras with a series operation, Minimum cost flow algorithms for series-parallel networks, Lattices of crosscuts, On the flow cost lowering problem, Axiomatizing the subsumption and subword preorders on finite and infinite partial words, Series parallel posets with nonfinitely generated clones, An algorithm for minimizing setups in precedence constrained scheduling, A comparison of point-based approaches to qualitative temporal reasoning, The quadratic 0-1 knapsack problem with series-parallel support, Profile Scheduling of Opposing Forests and Level Orders, The knapsack problem with special neighbor constraints, Describing the local structure of sequence graphs, Equational Theories of Scattered and Countable Series-Parallel Posets, Resource allocation via dynamic programming in activity networks, The two-machine flow shop problem with arbitrary precedence relations, A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks, Can transitive orientation make sandwich problems easier?, Positive Semidefinite Zero Forcing: Complexity and Lower Bounds, Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs, Nonfinite axiomatizability of the equational theory of shuffle, Efficient rewriting in cograph trace monoids, How to draw a series-parallel digraph, New Complexity Results and Algorithms for the Minimum Tollbooth Problem, Improving Selfish Routing for Risk-Averse Players, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs, Quadratic assignment problems on series-parallel digraphs, Unnamed Item, Entropic uniform sampling of linear extensions in series-parallel posets, ON SCHEDULING SERIES-PARALLEL DAGs TO MAXIMIZE AREA, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs, Chronological rectangle digraphs which are two-terminal series-parallel, Free shuffle algebras in language varieties extended abstract, Nonfinite axiomatizability of shuffle inequalities, The connected critical node problem, Robust minimum cost flow problem under consistent flow constraints, Generating Posets Beyond N, On Point-Sets That Support Planar Graphs, Minimum cost dynamic flows: The series-parallel case, An optimal algorithm for an outerplanar facility location problem with improved time complexity, How fast can we reach a target vertex in stochastic temporal graphs?, Complexité de problèmes liés aux graphes sans circuit, Languages under concatenation and shuffling, Minimum cost flows with minimum quantities, The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs, Automata-based Representations for Infinite Graphs, Typical sequences revisited -- computing width parameters of graphs, Cayley posets, Optimal Linear Extensions by Interchanging Chains, Improving spanning trees by upgrading nodes, Solutions for subset sum problems with special digraph constraints, A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths, A tight lower bound for primitivity in k-structures, Scheduling on Two Unbounded Resources with Communication Costs, GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE, On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data, Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs, Learning pomset automata, A note on integral generalized flows in directed partial 2-trees, Efficient computation of the oriented chromatic number of recursively defined digraphs, Cross-series-parallel digraphs, Extensions of Decision-Theoretic Troubleshooting: Cost Clusters and Precedence Constraints, Drawing graphs with attribute graph grammars, A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths, Riordan posets and associated incidence matrices, Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs, Shuffles and concatenations in the construction of graphs, Retractions onto series-parallel posets, On Maltsev digraphs, Maximum flows in generalized processing networks, Algorithms for core stability, core largeness, exactness, and extendability of flow games, The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations, Fully dynamic recognition algorithm and certificate for directed cographs, Algebraic and graph-theoretic properties of infiniten-posets, Complementation of Branching Automata for Scattered and Countable N-Free Posets, On characterizations for subclasses of directed co-graphs, Posets with maximal Möbius function, Maximum weight matching and genetic algorithm for fixed-shape facility layout problem, Logic and Bounded-Width Rational Languages of Posets over Countable Scattered Linear Orderings, Two-stage combinatorial optimization problems under risk, A branch and bound algorithm for the minimum storage-time sequencing problem, Minimum-cost strong network orientation problems: Classification, complexity, and algorithms, Linear time algorithms to solve the linear ordering problem for oriented tree based graphs, Lattice-based sum of t-norms on bounded lattices, Complexity and approximability of the maximum flow problem with minimum quantities, Earliest arrival flows on series-parallel graphs, Improving selfish routing for risk-averse players, Complementation of Branching Automata for Scattered and Countable Series-Parallel Posets, A polynomial algorithm for minDSC on a subclass of series Parallel graphs, Network Topologies for Weakly Pareto Optimal Nonatomic Selfish Routing, A review of four decades of time-dependent scheduling: main results, new topics, and open problems, Optimization Problems with Color-Induced Budget Constraints, NodeTrix planarity testing with small clusters, A Note on the Recognition of Nested Graphs, System Reliability Analysis in the Presence of Dependent Component Failures, Reversible Kleene lattices, Miscellaneous Digraph Classes, Linear time algorithms on mirror trees, Single-machine scheduling problems with precedence constraints and simple linear deterioration, Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier, On budget-constrained flow improvement., The robust shortest path problem in series -- parallel multidigraphs with interval data, A linear-time certifying algorithm for recognizing generalized series-parallel graphs, A Cryptographic Code Based on Digraphs, Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs, Synchronizing series-parallel deterministic finite automata with loops and related problems, Convex generalized flows, All subgraphs of a wheel are 5-coupled-choosable, A Lower Bound on the Area Requirements of Series-Parallel Graphs, Unnamed Item, Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time, Treelength of series-parallel graphs, Inefficiency of pure Nash equilibria in series-parallel network congestion games, The price of anarchy in series-parallel network congestion games, A System of Interaction and Structure III: The Complexity of BV and Pomset Logic, Robust transshipment problem under consistent flow constraints, Capacity-preserving subgraphs of directed flow networks, Measuring the distance to series-parallelity by path expressions, The complexity of the timetable‐based railway network design problem, Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints, Complexity of finding a join of maximum weight, Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality, Treemaps for Directed Acyclic Graphs, Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs, Unnamed Item, Logic and rational languages of scattered and countable series-parallel posets, Analyse de sensibilité pour les problèmes linéaires en variables 0-1