On the computational complexity of the minimum-dummy-activities problem in a pert network

DOI10.1002/NET.3230140104MaRDI QIDQ3332752zbMATH OpenOpenAlexFDO

Authors Maciej M. Sysło

Publication date 1984

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230140104

zbMATH Keywords

activity networkdummy activitiesevent networksNP-completenessPERT networkpolynomial-time algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35)

Recommendations

• The minimum dummy task problem
• A heuristic for constructing activity-on-arrow pert networks with minimal dummy activities
• A new method for constructing a minimal PERT network
• scientific article; zbMATH DE number 1234734
• scientific article; zbMATH DE number 1517143

Cited in

(17)

• A heuristic for constructing activity-on-arrow pert networks with minimal dummy activities
• Activity nets: A guided tour through some recent developments
• Parallel \(N\)-free order recognition
• Network decomposition-based benchmark results for the discrete time-cost tradeoff problem
• On the hardness of evaluating criticality of activities in a planar network with duration intervals
• Simplifying activity networks under generalized precedence relations to extended CPM networks
• A note on minimum-dummy-activities PERT networks
• The minimum dummy task problem
• Transitively reduced and transitively closed event networks
• scientific article; zbMATH DE number 1234734 (Why is no real title available?)
• scientific article; zbMATH DE number 1339495 (Why is no real title available?)
• scientific article; zbMATH DE number 1517143 (Why is no real title available?)
• Reducing the number of paths in a minimized project-network with given bounds on the durations of activities
• New heuristics for modeling temporal constraints and generating PERT network with minimum number of dummy-arcs
• Creating an equivalent multi-phases activity network by adding the least dummy activities
• A new method for constructing a minimal PERT network
• Optimal constructions of reversible digraphs

This page was built for publication: On the computational complexity of the minimum-dummy-activities problem in a pert network

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