transparent gif

 

Ej inloggad.

Göteborgs universitets publikationer

Minimum equivalent precedence relation systems

Författare och institution:
Kin Cheong Sou (Institutionen för matematiska vetenskaper, matematik, Chalmers/GU)
Publicerad i:
54th IEEE Conference on Decision and Control, CDC 2015, Osaka, Japan, 15-18 December 2015, s. 3299-3304
ISBN:
978-1-4799-7886-1
ISSN:
0743-1546
Publikationstyp:
Konferensbidrag, refereegranskat
Publiceringsår:
2015
Språk:
engelska
Fulltextlänk:
Sammanfattning (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.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
NATURVETENSKAP ->
Matematik ->
Diskret matematik
NATURVETENSKAP ->
Matematik ->
Beräkningsmatematik ->
Tillämpad matematik ->
Optimeringslära, systemteori
Chalmers styrkeområden:
Informations- och kommunikationsteknik
Chalmers fundament:
Grundläggande vetenskaper
Ytterligare information:
Article number 7402715
Postens nummer:
230478
Posten skapad:
2016-01-12 15:04
Posten ändrad:
2016-06-27 10:43

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007