Minimum equivalent precedence relation systems

DOI10.1016/J.DAM.2017.07.030MaRDI QIDQ2410264zbMATH OpenOpenAlexFDO

Authors Kin Cheong Sou

Publication date 17 October 2017

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

Full work available at URL https://arxiv.org/abs/1503.04753

zbMATH Keywords

linear inequality systemsminimum representation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In this paper two related simplification problems for systems of linear inequalities describing precedence relation systems are considered. Given a precedence relation system, the first problem seeks a minimum subset of the precedence relations (i.e., inequalities) which has the same solution set as that of the original system. The second problem is the same as the first one except that the ``subset restriction in the first problem is removed. This paper establishes that the first problem is NP-hard. However, a sufficient condition is provided under which the first problem is solvable in polynomial-time. In addition, a decomposition of the first problem into independent tractable and intractable subproblems is derived. The second problem is shown to be solvable in polynomial-time, with a full parameterization of all solutions described. The results in this paper generalize those in [Moyles and Thompson 1969, Aho, Garey, and Ullman 1972] for the minimum equivalent graph problem and transitive reduction problem, which are applicable to unweighted directed graphs.

Recommendations

• Review of properties of different precedence graphs for scheduling problems
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• Scheduling with AND/OR Precedence Constraints
• Publication:4952622
• `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders

Cites work

• A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags
• An Algorithm for Finding a Minimal Equivalent Graph of a Digraph
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• Approximating the Minimum Equivalent Digraph
• Consistency, redundancy, and implied equalities in linear systems
• scientific article; zbMATH DE number 2042673 (Why is no real title available?)
• Identifying Redundant Constraints and Implicit Equalities in Systems of Linear Constraints
• Introduction to algorithms.
• One-machine generalized precedence constrained scheduling problems
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Single machine scheduling subject to precedence delays
• The One-Machine Problem with Delayed Precedence Constraints and its Use in Job Shop Scheduling
• The Transitive Reduction of a Directed Graph

This page was built for publication: Minimum equivalent precedence relation systems

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