Back to search

University of Patras

ΔΙΑΤΑΞΕΙΣ ΔΙΑΓΡΑΦΩΝ, ΠΑΙΧΝΙΔΙΑ ΚΑΙ ΕΛΑΣΣΟΝΑ ΣΕ ΓΡΑΦΗΜΑΤΑ

Abstract

dc:description

IN 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/8692

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Θηλυκός, Δημήτριος. ΔΙΑΤΑΞΕΙΣ ΔΙΑΓΡΑΦΩΝ, ΠΑΙΧΝΙΔΙΑ ΚΑΙ ΕΛΑΣΣΟΝΑ ΣΕ ΓΡΑΦΗΜΑΤΑ. University of Patras, 1997. http://hdl.handle.net/10442/hedi/8692