A compact labelling scheme for series-parallel graphs

DOI10.1016/0166-218X(85)90079-4MaRDI QIDQ1079115zbMATH OpenFDO

Authors George Steiner

Publication date 1985

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(85)90079-4

zbMATH Keywords

linear time labeling algorithmsequencingseries-parallel graphsseries-parallel precedence constraints

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Recommendations

• Parallel algorithms for series parallel graphs
• Parallel recognition of series-parallel graphs
• Efficient parallel algorithms for series parallel graphs
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• scientific article; zbMATH DE number 1560506

Cites work

• `` Strong NP-Completeness Results
• A Dynamic Programming Approach to Sequencing Problems
• A linear algorithm for the domination number of a series-parallel graph
• Assembly-Line Balancing—Dynamic Programming with Precedence Constraints
• Complexity of Scheduling under Precedence Constraints
• Depth-First Search and Linear Graph Algorithms
• Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
• Fast Approximation Algorithms for Knapsack Problems
• scientific article; zbMATH DE number 3648418 (Why is no real title available?)
• scientific article; zbMATH DE number 3471786 (Why is no real title available?)
• scientific article; zbMATH DE number 3520146 (Why is no real title available?)
• Linear-time computability of combinatorial problems on series-parallel graphs
• On Dynamic Programming Methods for Assembly Line Balancing
• On graphs in which two vertices are distinguished
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Sequencing with Series-Parallel Precedence Constraints
• Single Machine Scheduling with Precedence Constraints of Dimension 2
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• The Recognition of Series Parallel Digraphs
• The Transitive Reduction of a Directed Graph
• The Two-Machine Maximum Flow Time Problem with Series Parallel Precedence Relations
• The Two-Machine Maximum Flow Time Problem with Series-Parallel Precedence Constraints: An Algorithm and Extensions
• Topology of series-parallel networks

Cited in

(5)

• Monotone labelings in polygonal tilings
• Solutions for subset sum problems with special digraph constraints
• Miscellaneous digraph classes
• Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
• A P-complete graph partition problem

This page was built for publication: A compact labelling scheme for series-parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079115)