Abstract
dc:descriptionIN THIS PH.D THESIS A SERIES OF PARAMETTERS, DEFINED IN TERMS OF LINEAR ORDERINGS ARE STUDIED. THE BASIC DIRECTIONS ARE THE INVESTIGATION OF THEIR COMPUTATIONAL COMPLEXITY, THE FINDING OF UPPER AND LOWER BOUNDS TO THEIR VALUES, THEIR RELATION WITH GRAPH SEARCHING PROBLEMS AND THEIR APPLICATION ON THE CONSTRAINT SATISFACTION PROBLEM AND THE ROUTING PROBLEM ON DISTRIBUTED COMPUTING SYSTEMS. THE BASIC RESULTS ARE THE FOLLOWING. 1) SUBLINEAR ALGORITHM FOR ENFORCING PARTIAL ARE CONSISTENCY ON NETWORKS OF CONSTRAINTS. 2) TIGHT UPPER AND LOWER BOUND FOR THE GRAPH THEORETIC PARAMETER OF J - LINKAGE AND STUDY OF ITS PARALLEL COMPUTABILITY AND APPROXIMABILITY. 3) STUDY OF THE PARALLEL COMPUTABILITY AND APPROXIMABILITY OF THE ARC CONSISTENCY PROBLEM. 4) CONSTRUCTION OF A GRAPH THEORETIC SEARCH GAME FOR THE PARAMETERS OF WIDTH AND TREEWIDTH OF A GRAPH AND STUDY OF THE BEHAVIOR OF THIS GAME ON GRAPHS WITH BOUNDED CHORDALITY. 5) EXCLUSION (AS A MINOR) OF THE GRAPH K2,R FROM GENERAL AND PLANAR GRAPHS. 6) PROOF OF THE CLOSSEDNESS UNDER TAKING OF MINORS OF THE CLASS OF GRAPHS ON WHICH THERE EXISTS AN OPTIMAL K - INTERVAL ROUTING SCHEME AND PARTIAL CHARACTERISATION OF THEIR STRUCTURE THOUGH THE FINDING OF AN UPPER BOUND TO THEIR TREEWIDTH.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 1997
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Θηλυκός, Δημήτριος
Subjects
dc:subject × 24- Αλγόριθμοι
- Δεντρόπλατος
- ΔΕΣΜΩΣΗ ΓΡΑΦΗΜΑΤΟΣ
- ΔΙΚΤΥΟ ΠΕΡΙΟΡΙΣΜΩΝ
- ΔΡΟΜΟΛΟΓΗΣΗ ΔΙΑΣΤΗΜΑΤΩΝ
- ΕΛΑΣΣΟΝΑ ΓΡΑΦΗΜΑΤΑ
- Παίγνια σε γραφήματα
- ΠΑΡΑΛΛΗΛΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ
- Algorithms
- CONSTRAINT NETWORK
- GAMES ONGRAPHS
- Graph minors
- INTERVAL ROUTING
- LINKAGE OF A GRAPH
- PARALLEL COMPLEXITY
- TREEWIPTH
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/8692