CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Minimum equivalent precedence relation systems

Kin Cheong Sou (Institutionen för matematiska vetenskaper, matematik)
54th IEEE Conference on Decision and Control, CDC 2015, Osaka, Japan, 15-18 December 2015 (0743-1546). p. 3299-3304. (2015)
[Konferensbidrag, refereegranskat]

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.


Article number 7402715



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2016-01-12. Senast ändrad 2016-06-27.
CPL Pubid: 230478

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Informations- och kommunikationsteknik
Diskret matematik
Optimeringslära, systemteori

Chalmers infrastruktur