UNIVERSITÄTSBIBLIOTHEK
  • search hit 12 of 20
Back to Result List

Matrices with the consecutive ones property, interval graphs and their applications

  • Matrices with the consecutive ones property and interval graphs are important notations in the field of applied mathematics. We give a theoretical picture of them in first part. We present the earliest work in interval graphs and matrices with the consecutive ones property pointing out the close relation between them. We pay attention to Tucker's structure theorem on matrices with the consecutive ones property as an essential step that requires a deep considerations. Later on we concentrate on some recent work characterizing the matrices with the consecutive ones property and matrices related to them in the terms of interval digraphs as the latest and most interesting outlook on our topic. Within this framework we introduce a classiffcation of matrices with consecutive ones property and matrices related to them. We describe the applications of matrices with the consecutive ones property and interval graphs in different fields. We make sure to give a general view of application and their close relation to our studying phenomena. Sometimes we mention algorithms that work in certain fields. In the third part we give a polyhedral approach to matrices with the consecutive ones property. We present the weighted consecutive ones problem and its relation to Tucker's matrices. The constraints of the weighted consecutive ones problem are improved by introducing stronger inequalities, based on the latest theorems on polyhedral aspect of consecutive ones property. Finally we implement a separation algorithm of Oswald and Reinhelt on matrices with the consecutive ones property. We would like to mention that we give a complete proof to the theorems when we consider important within our framework. We prove theorems partially when it is worthwhile to have a closer look, and we omit the proof when there are is only an intersection with our studying phenomena.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Dritan Osmani
URN (permanent link):urn:nbn:de:hbz:386-kluedo-11651
Document Type:Diploma Thesis
Language of publication:English
Year of Completion:2001
Year of Publication:2001
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2001/06/28
Tag:consecutive ones polytopes; consecutive ones property; interval graphs; monotone consecutive arrangement; separation problem
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011