### Skapa referens, olika format (klipp och klistra)

**Harvard**

Sou, K. (2015) *Minimum equivalent precedence relation systems*.

** BibTeX **

@conference{

Sou2015,

author={Sou, Kin Cheong},

title={Minimum equivalent precedence relation systems},

booktitle={54th IEEE Conference on Decision and Control, CDC 2015, Osaka, Japan, 15-18 December 2015},

isbn={978-1-4799-7886-1},

pages={3299-3304},

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 equivalent subset of the precedence relations (i.e., inequalities) which has the same solution set as that of the original system. The second problem is similar to the first one, but the minimum equivalent system need not be a subset of the original system. This paper shows that the first problem is NP-hard. However, a sufficient condition is derived 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.},

year={2015},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 230478

A1 Sou, Kin Cheong

T1 Minimum equivalent precedence relation systems

YR 2015

T2 54th IEEE Conference on Decision and Control, CDC 2015, Osaka, Japan, 15-18 December 2015

SN 978-1-4799-7886-1

SP 3299

OP 3304

AB 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 equivalent subset of the precedence relations (i.e., inequalities) which has the same solution set as that of the original system. The second problem is similar to the first one, but the minimum equivalent system need not be a subset of the original system. This paper shows that the first problem is NP-hard. However, a sufficient condition is derived 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.

LA eng

DO 10.1109/CDC.2015.7402715

LK http://dx.doi.org/10.1109/CDC.2015.7402715

OL 30