A compact labelling scheme for series-parallel graphs
From MaRDI portal
Publication:1079115
DOI10.1016/0166-218X(85)90079-4zbMath0596.90049MaRDI QIDQ1079115
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
sequencingseries-parallel graphslinear time labeling algorithmseries-parallel precedence constraints
Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Directed graphs (digraphs), tournaments (05C20)
Related Items
Monotone labelings in polygonal tilings ⋮ Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs ⋮ Solutions for subset sum problems with special digraph constraints ⋮ Miscellaneous Digraph Classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear algorithm for the domination number of a series-parallel graph
- Topology of series-parallel networks
- On graphs in which two vertices are distinguished
- A Dynamic Programming Approach to Sequencing Problems
- Single Machine Scheduling with Precedence Constraints of Dimension 2
- The Two-Machine Maximum Flow Time Problem with Series-Parallel Precedence Constraints: An Algorithm and Extensions
- Fast Approximation Algorithms for Knapsack Problems
- The Two-Machine Maximum Flow Time Problem with Series Parallel Precedence Relations
- Sequencing with Series-Parallel Precedence Constraints
- Single Machine Scheduling with Series-Parallel Precedence Constraints
- The Recognition of Series Parallel Digraphs
- On Dynamic Programming Methods for Assembly Line Balancing
- Linear-time computability of combinatorial problems on series-parallel graphs
- Complexity of Scheduling under Precedence Constraints
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- `` Strong NP-Completeness Results
- Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
- On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
- Assembly-Line Balancing—Dynamic Programming with Precedence Constraints
- The Transitive Reduction of a Directed Graph
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: A compact labelling scheme for series-parallel graphs
