The closed neighbourhood of a vertex in a graph is the vertex together with the set of adjacent vertices. A di®erentiating-dominating set, or identifying code, is a collection of vertices whose intersection with the closed neighbour- hoods of each vertex is distinct and nonempty. A di®erentiating-dominating set in a graph serves to uniquely identify all the vertices in the graph. Chapter 1 begins with the necessary de¯nitions and background results and provides motivation for the following chapters. Chapter 1 includes a summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de- ¯nes co-distinguishable graphs and determines bounds on the number of edges in graphs which are distinguishable and co-distinguishable while Chap- ter 3 describes the maximum number of vertices needed in order to identify vertices in a graph, and includes some Nordhaus-Gaddum type results for the sum and product of the di®erentiating-domination number of a graph and its complement. Chapter 4 explores criticality, in which any minor modi¯cation in the edge or vertex set of a graph causes the di®erentiating-domination number to change. Chapter 5 extends the identi¯cation parameters to allow for orientations of the graphs in question and considers the question of when adding orientation helps reduce the value of the identi¯cation parameter. We conclude with a survey of complexity results in Chapter 6 and a collection of interesting new research directions in Chapter 7. / Mathematical Sciences / PhD (Mathematics)

The lower and upper independent, domination and irredundant numbers of the graph G = (V, E) are denoted by i ( G) , f3 ( G), 'Y ( G), r ( G), ir ( G) and IR ( G) respectively. These six numbers are called the domination parameters. For each of these parameters n:, we define six types of criticality. The graph G is n:-critical (n:+ -critical) if the removal of any vertex of G causes n: (G) to decrease (increase), G is n:-edge-critical (n:+-edge-critical) if the addition of any missing edge causes n: (G) to decrease (increase), and G is Ir-ER-critical (n:- -ER-critical) if the removal of any edge causes n: (G) to increase (decrease). For all the above-mentioned parameters n: there exist graphs which are n:-critical, n:-edge-critical and n:-ER-critical. However, there do not exist any n:+-critical graphs for n: E {ir,"f,i,/3,IR}, no n:+-edge-critical graphs for n: E {ir,"f,i,/3} and non:--ER-critical graphs for: E {'Y,/3,r,IR}. Graphs which are "I-critical, i-critical, "I-edge-critical and i-edge-critical are well studied in the literature. In this thesis we explore the remaining types of criticality. We commence with the determination of the domination parameters of some wellknown classes of graphs. Each class of graphs we consider will turn out to contain a subclass consisting of graphs that are critical according to one or more of the definitions above. We present characterisations of "I-critical, i-critical, "I-edge-critical and i-edge-critical graphs, as well as ofn:-ER-critical graphs for n: E {/3,r,IR}. These characterisations are useful in deciding which graphs in a specific class are critical. Our main results concern n:-critical and n:-edge-critical graphs for n: E {/3, r, IR}. We show that the only /3-critical graphs are the edgeless graphs and that a graph is IRcritical if and only if it is r-critical, and proceed to investigate the r-critical graphs which are not /3-critical. We characterise /3-edge-critical and r-edge-critical graphs and show that the classes of IR-edge-critical and r-edge-critical graphs coincide. We also exhibit classes of r+ -critical, r+ -edge-critical and i- -ER-critical graphs. / Mathematical Sciences / D. Phil. (Mathematics)

Dans cette thèse nous montrons que le raisonnement symbolique associé à la vérification de la consistance d'arc avec propagation de contraintes est un outil efficace pour interpréter les images. Nous montrons dans un premier temps que ce cadre théorique permet de vérifier l'organisation spatiale de différentes composantes d'un objet complexe dans une image. Nous proposons ensuite d'étendre l'utilisation de celui-ci à la reconnaissance sélective des formes décrites par des équations mathématiques, grâce à la notion de consistance d'hyper-arc à deux niveaux de contraintes. La pertinence et la faisabilité de cette approche ont été validées par de multiples tests. En outre, les résultats obtenus sur des images sur-segmentées montrent que la méthode proposée est résistante au bruit, même dans des conditions où les humains (dans certains cas d'agnosie visuelle) peuvent échouer. Ces résultats soutiennent l'intérêt du raisonnement symbolique dans la compréhension de l'image. / In this thesis we show that symbolic reasoning associated with arc consistency checking is an efficient tool for images interpretation. We first show that this theoretical framework makes it possible to verify the spatial organization of different components of a complex object in an image. We then propose to extend the use of this framework to the selective recognition of shapes described by mathematical equations, thanks to the notion of hyper-arc consistency with bi-levels constraint. The relevance and feasibility of this approach have been validated by multiple tests. In addition, the results obtained on over-segmented images show that the proposed method is noise-resistant, even under conditions where humans (in some cases visual agnosia) may fail. These results support the interest of symbolic reasoning in image understanding.

Σε αυτήν την εργασία, προσεγγίζουμε την συνύπαρξη δύο βασικών αλγεβρικών δομών για τις ανάγκες επίλυσης πολλών προβλημάτων των σύγχρονων Μαθηματικών. Οι δομές αυτές είναι οι ομάδες και τα γραφήματα, που με την ταυτόχρονη χρήση τους μας οδήγησαν στην μελέτη των G-γραφημάτων. Ειδικότερα θα δούμε τον τρόπο με τον οποίο η θεωρία ομάδων βοηθά στην μελέτη των γραφημάτων και πως η θεωρία γραφημάτων ανταποδίδει τη βοήθεια αυτή. Όλα αυτά, προσδιορίζονται-μελετώνται και επεκτείνονται με την υποστήριξη που προσφέρει στις μέρες μας η Υπολογιστική Άλγεβρα. Ο κλάδος αυτός των μαθηματικών υποβοηθούμενος από αλγορίθμους και υπολογιστικά αλγεβρικά συστήματα καθοδήγησε και υποστήριξε την μελέτη «δύσκολων» προβλημάτων. Αναμένεται να επεκτείνει τη μελέτη και την επίλυση και άλλων ανοικτών προβλημάτων στο μέλλον. Αναδεικνύεται κατά αυτό τον τρόπο, η αξία και η σπουδαιότητα της χρήσης υπολογιστικών μεθόδων ως σημαντικού εργαλείου στην μελέτη γραφημάτων και ομάδων. Η εργασία έχει οργανωθεί σε εννέα κεφάλαια. Αρχικά γίνεται αναφορά στην Υπολογιστική Άλγεβρα. Υπολογιστική Άλγεβρα είναι ο κλάδος των Μαθηματικών ο οποίος ασχολείται με τις τεχνικές που εκτελούν τους αλγεβρικούς υπολογισμούς με την βοήθεια των υπολογιστών. Η λογική διαδικασία που χρησιμοποιεί φτιάχνεται από τις βασικές θεωρίες των μαθηματικών θεμάτων που επεξεργάζονται και επεκτείνονται από : 1) αλγορίθμους και δομές δεδομένων 2) γλώσσες προγραμματισμού και συστήματα λογισμικού 3) μέσα διασύνδεσης ανάμεσα στα αλγεβρικά υπολογιστικά συστήματα και τους χρησιμοποιούμενους αλγορίθμους. Οι «υπολογισμοί» πάνω σε διάφορα θέματα, είχαν απασχολήσει τον άνθρωπο από τα παλιά χρόνια γιατί πάντα ήθελε να δώσει λύσεις στα προβλήματά του. Στις μέρες μας, υπολογίζουμε περισσότερο για ερευνητικούς λόγους, για να επεκτείνουμε τους ήδη υπάρχοντες αλγορίθμους σε ευρύτερες περιοχές και για να επιλύσουμε σύγχρονα προβλήματα της επιστήμης. Πολλά από τα προβλήματα που σήμερα είναι “μη επιλύσιμα” στα Μαθηματικά, αφορούν στις Ομάδες. Στα Μαθηματικά Ομάδα (group) είναι ένα σύνολο, μαζί με μία διμελή πράξη (όπως ο πολλαπλασιασμός και η πρόσθεση) που ικανοποιούν βασικά αξιώματα που περιγράφονται λεπτομερώς στο κεφάλαιο 2 της εργασίας. Η σημασία των ομάδων στα Μαθηματικά είναι μεγάλη. Πολλά από τα αντικείμενα που ερευνώνται στα μαθηματικά είναι ομάδες. Γνωστά σύνολα αριθμών, όπως οι ακέραιοι, οι ρητοί, οι πραγματικοί και οι μιγαδικοί αριθμοί εφοδιασμένα με την πράξη της πρόσθεσης είναι ομάδες. Η θεωρία ομάδων θεμελιώνει τις ιδιότητες αυτών των συστημάτων και ανακαλύπτει πολλές άλλες. Τα αποτελέσματά της είναι ευρέως εφαρμόσιμα. Σημαντική αναφορά γίνεται στην ομάδα των μεταθέσεων n αντικειμένων (συμμετρική ομάδα) και την εναλλακτική ομάδα (είναι η ομάδα άρτιου αριθμού μεταθέσεων η αντικειμένων). Ενδιαφέρον θέμα είναι η δημιουργία νέων ομάδων από τις παλιές. Έτσι γίνεται σημαντικός ο ρόλος της υποομάδας, αλλά και των διαμερίσεων των ομάδων, πράγμα που επιτυγχάνεται ικανοποιητικά με την βοήθεια των «συνσυνόλων», της υποομάδας και των τροχιών (orbits). Ιδιαίτερο ρόλο στην θεωρία των ομάδων παίζουν οι μορφισμοί που μελετούν τις σχέσεις ανάμεσα στις ομάδες και ορίζονται με ειδικές συναρτήσεις οι οποίες παίρνουν αντικείμενα από μία ομάδα και τα αντιστοιχούν σε μία άλλη Εξετάζοντας τους μορφισμούς μας επιτρέπεται να κάνουμε σημαντική ανάλυση των σχέσεων ανάμεσα στις ομάδες. Επίσης οι μορφισμοί με τις αντιστοιχίσεις τους συνδέουν τις ομάδες με τα γραφήματα. Οι ομάδες υπογραμμίζουν πολλές άλλες αλγεβρικές δομές όπως τα πεδία και τα διανύσματα χώρου. Είναι επίσης σημαντικά εργαλεία για την μελέτη της συμμετρίας σε όλους τους τύπους. Η άποψη ότι η συμμετρία ενός αντικειμένου σχηματίζει μια ομάδα είναι θεμελιώδης για πολλά Μαθηματικά. Γι αυτές τις αιτίες η Θεωρία ομάδων είναι μια σημαντική περιοχή στα μοντέρνα μαθηματικά και με πολλές εφαρμογές σε άλλους κλάδους όπως η φυσική. Τα γραφήματα(graphs), τα κατευθυνόμενα γραφήματα (directed graphs) και τα δέντρα (trees) εμφανίζονται σε πολλές περιοχές των Μαθηματικών και της επιστήμης των Υπολογιστών. Το κεφάλαιο 3 καλύπτει αυτά τα θέματα. Το γράφημα πολλών προβλημάτων, που αναφέρονται σε διακριτά αντικείμενα και διμελείς σχέσεις, είναι μία πολύ βολική μορφή αναπαράστασης. Αυτό μας οδήγησε στην μελέτη της θεωρίας των γραφημάτων. Τα γραφήματα έπαιξαν και παίζουν σημαντικότατο ρόλο στην ανάπτυξη αλγορίθμων, καθώς είναι τα μόνα εργαλεία στα μαθηματικά που μπορούν να παραστήσουν μία αλληλουχία σκέψεων. Στη θεωρία των γραφημάτων ορίζονται οι “περίπατοι”(walks), οι “αποστάσεις” (distances), τα “υπογραφήματα” (subgraphs) και τέλος οι “μορφισμοί” (morphisms) που είναι ανάλογοι με εκείνους των ομάδων. Ιδιαίτερο ρόλο παίζει η συνδεσιμότητα (connectivity), κυρίαρχη δε για τους αλγορίθμους είναι η έννοια του “δέντρου” (tree). Δύο σημαντικά αλγοριθμικά προβλήματα που απασχολούν τους επιστήμονες είναι Α) ο έλεγχος δύο γραφημάτων ως προς τον ισομορφισμό Β) η εύρεση της ομάδας αυτομορφισμού ενός γραφήματος Τα παραπάνω προβλήματα δεν είναι πάντοτε επιλύσιμα. Εντούτοις σε μερικές περιπτώσεις μπορούν να επιλυθούν με τη βοήθεια αλγορίθμων που υποστηρίζονται από τα υπολογιστικά συστήματα GAP, NAUTY, και MAGMA Συνεχίζοντας στα κεφάλαια 4,5,6 κάνουμε μία μικρή περιγραφή στα κυριότερα για τους παραπάνω στόχους υπολογιστικά αλγεβρικά συστήματα. Η κύρια χρήση των υπολογιστικών αυτών συστημάτων είναι η σύνδεση των παραπάνω δομών (ομάδων και γραφημάτων). Εστιάζουν στους υπολογισμούς των μεταθέσεων n στοιχείων, τον υπολογισμό των μορφισμών των ομάδων, των συνσυνόλων, των τροχιών και των πυρήνων. Το αλγεβρικό Υπολογιστικό Σύστημα GAP, (Groups, Algorithms, Programming) περιέχει ένα «ανοικτό» λογισμικό στο χρήστη, πράγμα που σημαίνει ότι μπορεί κανείς να γράψει τα δικά του προγράμματα στη γλώσσα GAP και να τα χρησιμοποιήσει ακριβώς με τον ίδιο τρόπο όπως και τα προγράμματα τα οποία αποτελούν μέρος του συστήματος. Από την άλλη μεριά το ίδιο είναι εφοδιασμένο με μία μεγάλη βιβλιοθήκη συναρτήσεων η οποία υποστηρίζει αλγεβρικούς και άλλους αλγορίθμους. Αρχικά όλα τα προγράμματα της GAP βιβλιοθήκης ήταν γραμμένα στη γλώσσα προγραμματισμού C, τώρα όμως όλα τα προγράμματα έχουν γραφτεί στη γλώσσα GAP. Στο τέλος του κεφαλαίου 4, δίνονται παραδείγματα εφαρμογής προγραμμάτων του GAP πάνω στους ομοιομορφισμούς των ομάδων. To nauty (no automorphisms, yes?) είναι ένα σύνολο διαδικασιών για προσδιορισμό του αυτομορφισμού μιας ομάδας από ένα γράφημα χρωματισμένων κορυφών. Παρουσιάζει αυτήν την πληροφορία αφού του δοθεί ένα σύνολο γεννητόρων, το μέγεθος της ομάδας και ο αριθμός των τροχιών της ομάδας. Μπορεί επίσης να δώσει έναν ισομορφισμό του γραφήματος. Ο αλγόριθμος που χρησιμοποιεί το nauty είναι μία προς τα πίσω διαδρομή που μπορεί να περιγραφεί σε ομάδες ενός συνηθισμένου δέντρου αναζήτησης. Διάφορα μεγέθη και παράμετροι καθορίζουν την πορεία της διαδικασίας, της οποίας η έξοδος δίνεται σε επίπεδα. Το magma, είναι ένα υπολογιστικό αλγεβρικό σύστημα, σχεδιασμένο να επιλύει προβλήματα στην Άλγεβρα, στη Θεωρία Αριθμών, στη Γεωμετρία και σε συνδυασμούς των παραπάνω Μαθηματικών θεμάτων. Μπορεί να αναπτύξει «εκλεπτυσμένα Μαθηματικά», τα οποία είναι υπολογιστικά δύσκολα. Παρέχει ένα αυστηρό Μαθηματικό περιβάλλον, το οποίο δίνει έμφαση στον διαρθρωτικό υπολογισμό. Ένα χαρακτηριστικό κλειδί είναι η δυνατότητα να συναρμολογεί κανονικές αντιπροσωπεύσεις δομών. Τα κύρια χαρακτηριστικά του είναι: α) αλγεβρική φιλοσοφία σχεδιασμού, β) καθολικότητα, γ) ενοποίηση, δ) παρουσίαση. Το πρόγραμμα, παρέχει στο χρήστη μία συλλογή βιβλιοθηκών και αρχείων τεκμηρίωσης που βρίσκονται όλες σε έναν κατάλογο που το ίδιο περιέχει. Η μελέτη των G-graphs στο κεφάλαιο 7 έχει οργανωθεί ως εξής: Πρώτα δίνουμε τον ορισμό ενός G-graph. Έπειτα περιγράφουμε μερικούς βασικούς αλγορίθμους για συνδυασμούς ομάδων οι οποίοι χρησιμοποιούνται στην μελέτη των G-graphs. Μετά θα συζητήσουμε την αποτελεσματική αποθήκευση και δομή των G-graphs, και πώς να χρησιμοποιηθεί ένας μεταβαλλόμενος τύπος για να υπολογίζει αποτελεσματικά πολλές ιδιότητες ενός G-graph. Στη συνέχεια συγκεντρώνουμε τις μεθόδους που χρησιμοποιούνται, με τη χρήση του NAUTY. Στο κεφάλαιο 8 μας απασχολεί η ταξινόμηση των γραφημάτων που είναι μεταβατικά ως προς την απόσταση (distance transitive graphs). Αυτά είναι τα γραφήματα των οποίων οι ομάδες αυτομορφισμού είναι μεταβατικές πάνω σε κάθε σύνολο ζευγαριών κορυφών σε απόσταση i, για i=0,1,2,.. Παρουσιάζεται μία εισαγωγή σε αυτήν την κατηγορία γραφημάτων και θεωρήματα από τα οποία διέπονται. Με τη χρήση της κατηγορίας των πεπερασμένων απλών ομάδων, φαίνεται πιθανό να βρεθούν όλα τα γραφήματα που είναι μεταβατικά ως προς την απόσταση. Τέλος στο κεφάλαιο 9 μελετάται η έννοια της απαρίθμησης συνσυνόλων (coset enumeration) που τα παραπάνω υπολογιστικά συστήματα προσπαθούν επίσης να αντιμετωπίσουν. Απαρίθμηση συνσυνόλων είναι το πρόβλημα της μέτρησης των συνσυνόλων μιας υποομάδας Η μιας ομάδας G. Η απαρίθμηση συνσυνόλων είναι μια από τις παλαιότερες και πιο χρήσιμες μεθόδους της υπολογιστικής θεωρίας ομάδων. Το 1936 οι Τodd και Coxeter ανακάλυψαν μία διαδικασία για να απαριθμούν τα συνσύνολα μιας υποομάδας από μία ομάδα. Αυτό αποδείχτηκε ένα ισχυρό εργαλείο για τη μελέτη των πεπερασμένων “παρουσιαζόμενων” ομάδων (presented groups) στην υπολογιστική θεωρία τoυς. Παλιότερα το 1911, ο Dehm πρότεινε την επίλυση του “Προβλήματος των λέξεων”. Αυτό είναι η εύρεση ενός αλγορίθμου που να αποφασίζει αν σε μία ομάδα που ορίζεται από ένα πεπερασμένο σύνολο γεννητόρων (generators) και σχέσεων (relators), μία λέξη (word) στους γεννήτορες παριστάνει το ταυτοτικό στοιχείο (identical element). Το πρόβλημα που έθεσε ο Dehn προσπάθησαν πολλοί αργότερα να επιλύσουν με τοπολογικούς στοχασμούς. Σήμερα, η περιοχή αυτή της Υπολογιστικής Θεωρίας των ομάδων έχει αναπτυχθεί γρήγορα μέσω του σχεδιασμού , της ανάπτυξης και της εφαρμογής των Αλγορίθμων, καθώς και εξαιτίας του αυξανομένου αριθμού των Μαθηματικών επιστημόνων που έχουν εργαστεί πάνω σε αυτά τα θέματα. Στο κεφάλαιο 9 δίνουμε μία μικρή περιγραφή του αλγορίθμου των Todd-Coxeter. Αξίζει να σημειωθεί ότι το πρόβλημα των λέξεων σήμερα είναι επιλύσιμο για πολλές όχι όμως όλες τις ομάδες. / This subject is a descrription of the computer algebric systems GAP,NAUTY, MAGMA.

The closed neighbourhood of a vertex in a graph is the vertex together with the set of adjacent vertices. A di®erentiating-dominating set, or identifying code, is a collection of vertices whose intersection with the closed neighbour- hoods of each vertex is distinct and nonempty. A di®erentiating-dominating set in a graph serves to uniquely identify all the vertices in the graph. Chapter 1 begins with the necessary de¯nitions and background results and provides motivation for the following chapters. Chapter 1 includes a summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de- ¯nes co-distinguishable graphs and determines bounds on the number of edges in graphs which are distinguishable and co-distinguishable while Chap- ter 3 describes the maximum number of vertices needed in order to identify vertices in a graph, and includes some Nordhaus-Gaddum type results for the sum and product of the di®erentiating-domination number of a graph and its complement. Chapter 4 explores criticality, in which any minor modi¯cation in the edge or vertex set of a graph causes the di®erentiating-domination number to change. Chapter 5 extends the identi¯cation parameters to allow for orientations of the graphs in question and considers the question of when adding orientation helps reduce the value of the identi¯cation parameter. We conclude with a survey of complexity results in Chapter 6 and a collection of interesting new research directions in Chapter 7. / Mathematical Sciences / PhD (Mathematics)

L’utilisation des réseaux de transport est conditionnée par l’efficacité et la simplicité de leur utilisation. En réponse à une mobilité exacerbée, volontaire ou subie, l’offre de transport se développe et motive tout à la fois, en un cycle continu, des déplacements encore plus exigeants. De manière complémentaire, la mobilité est bousculée par l’arrivée de nouvelles modalités de transport pouvant faire émerger, comme dans le cadre du covoiturage, des acteurs ou des pratiques jusqu’alors inexistants. Si la technologie permet de suivre cette évolution dans les services d’information aux voyageurs, il reste toujours à satisfaire des attentes déterminées par des usages en constante évolution. C’est de ce point de vue que l’obtention de chemins multiples pour relier une origine à une destination est un facteur qui n’est plus à négliger, surtout dans des réseaux de transport denses et comportant de nombreux modes et lignes de transport. Une liberté dans le choix laissé à l’utilisateur du réseau réduit les sentiments d’exclusion, d’incompréhension ou d’anxiété qui peuvent survenir face à une application logicielle ou sur internet et qui effectuent des choix arbitraires de façon autoritaire. De plus, cela permet de vérifier la qualité de l’offre de transport, car plus il existe de moyens différents pour effectuer un trajet dans un intervalle de temps donné, meilleur est le service. Cette thèse s’intéresse au calcul de telles alternatives par le biais de l’énumération par coût croissant des chemins entre deux points, puis par le filtrage de ceux-ci suivant des critères, supposés quelconques et laissés à l’appréciation des professionnels de transport qui peuvent ainsi faire varier les angles d’analyses de leurs offres.Par ailleurs, la synchronisation de trajets de plusieurs utilisateurs, en vue d’usages sociaux ou de déplacements mutualisés, est étudiée dans ce manuscrit sous l’angle du covoiturage. En ne considérant que deux usagers, l’objectif est de minimiser le temps de trajet global des participants sous la contrainte qu’ils partagent une partie de leur chemin entre un point de rencontre et un point de séparation qu’il faut alors déterminer. Sont également étudiées les variantes associées au changement des conditions de transport de chacun des participants comme l’établissement d’une origine ou d’une destination commune parallèlement à des contraintes sur les heures de départ ou d’arrivée des usagers. Enfin, puisque la voiture est très souvent pénalisée par la prise en charge d’un piéton, il convient d’étudier comment ce détour peut être contraint et les impacts sur les gains que cette limitation engendre.Cette thèse a été réalisée dans un contexte CIFRE pour la société MobiGIS. Lestravaux qui s’y rapportent ont fait l’objet de réalisations pratiques tant pour fournirdes solutions de mobilité dans le cadre des activités de l’entreprise que pour évaluerexpérimentalement les performances des algorithmes proposés pour les résoudre. / Efficiency and simplicity are two conditions upon which the use of a transportation system is relevant. May it be intentional or imposed, an increasing mobility triggers the need to enhance the transportation offer. In turn, such a response encourages an even more demanding mobility in a constantly adapting cycle. In parallel, new and forthcoming means of transportation emerge from time to time with unknown practices and renewed actors : exactly like what carpooling is stirring at the moment. Passenger information systems can technically deal with such evolutions thanks to improved technologies but they still struggle to keep up with constantly changing usage expectations.From this perspective the computation of several paths from an origin to a destination becomes increasingly relevant. This issue is even more crucial in dense transportation networks in which many modes and lines of transportation are combined. Indeed, giving some traveling choices to the end user reduces the feeling of exclusion, anxiety and the lack of understanding which may arise when facing arbitrary decisions dictated by a software or an Internet application. It is also helpful to estimate the quality of the transportation offer since the more paths exist to go from point A to point B within a fixed time window, the better the service is. This thesis focuses on the computation of such alternatives by the gradually increasing enumeration of paths between two points. Given this input, the pruning necessary to obtain such a diverse selection is assumed not to be known in advance. It is left up to transportation professionals who may choose a fitted solution based on their specific knowledge and objectives.Another subject studied in this thesis concerns the itinerary synchronization of several users for various social uses such as shared travels. It is here seen from the perspective of carpooling. Considering only two users, the problem is to minimize the traveling cost of the users under the constraint that they must share some part of their respective trips with one another. Solving this problem is equivalent to finding a pick up point and a drop off location between which both paths overlap. Multiple corner cases concerning the transportation conditions of each user as well as the special cases of shared origins or destinations are studied. The constraints on the arrival and/or departure times may also vary. Last but not least and since the driver is often penalized when giving up a lift, the restriction to a maximal detour the driver accepts, compared to his shortest path, is analyzed with respect to the benefits such a limitation generates.This thesis was funded by the MobiGIS company under the CIFRE (Industrial Agreement of Training through Research) researching context. The related work consisted in the practical implementation of mobility solutions within the framework of the company as well as the experimental performances evaluation of the algorithms proposed to solve them.

The lower and upper independent, domination and irredundant numbers of the graph G = (V, E) are denoted by i ( G) , f3 ( G), 'Y ( G), r ( G), ir ( G) and IR ( G) respectively. These six numbers are called the domination parameters. For each of these parameters n:, we define six types of criticality. The graph G is n:-critical (n:+ -critical) if the removal of any vertex of G causes n: (G) to decrease (increase), G is n:-edge-critical (n:+-edge-critical) if the addition of any missing edge causes n: (G) to decrease (increase), and G is Ir-ER-critical (n:- -ER-critical) if the removal of any edge causes n: (G) to increase (decrease). For all the above-mentioned parameters n: there exist graphs which are n:-critical, n:-edge-critical and n:-ER-critical. However, there do not exist any n:+-critical graphs for n: E {ir,"f,i,/3,IR}, no n:+-edge-critical graphs for n: E {ir,"f,i,/3} and non:--ER-critical graphs for: E {'Y,/3,r,IR}. Graphs which are "I-critical, i-critical, "I-edge-critical and i-edge-critical are well studied in the literature. In this thesis we explore the remaining types of criticality. We commence with the determination of the domination parameters of some wellknown classes of graphs. Each class of graphs we consider will turn out to contain a subclass consisting of graphs that are critical according to one or more of the definitions above. We present characterisations of "I-critical, i-critical, "I-edge-critical and i-edge-critical graphs, as well as ofn:-ER-critical graphs for n: E {/3,r,IR}. These characterisations are useful in deciding which graphs in a specific class are critical. Our main results concern n:-critical and n:-edge-critical graphs for n: E {/3, r, IR}. We show that the only /3-critical graphs are the edgeless graphs and that a graph is IRcritical if and only if it is r-critical, and proceed to investigate the r-critical graphs which are not /3-critical. We characterise /3-edge-critical and r-edge-critical graphs and show that the classes of IR-edge-critical and r-edge-critical graphs coincide. We also exhibit classes of r+ -critical, r+ -edge-critical and i- -ER-critical graphs. / Mathematical Sciences / D. Phil. (Mathematics)

Avec le développement des applications temps-réel sur Internet, telles que la télévision, la voix sur IP et les jeux en ligne, les fournisseurs d'accès à Internet doivent faire face à des contraintes de plus en plus fortes quant aux performances de leurs services. Cependant, après chaque changement topologique, les protocoles de routage à état des liens, utilisés dans les réseaux de cœur de ces opérateurs, entrent dans une période de convergence durant laquelle des boucles de routage peuvent apparaître. Ce phénomène dégrade les performances du réseau (latence, congestions, pertes de paquets) et peut durer plusieurs secondes. Dans le cadre de cette thèse, nous proposons de nouvelles solutions permettant de prévenir ces perturbations dans le cas de reconfigurations sur un lien ou un routeur. Notre approche a pour particularité de ne reposer que sur les mécanismes de base des protocoles de routage à état des liens, et d’être ainsi déployable de manière incrémentale dans n’importe quel réseau. Intuitivement, il s’agit de contrôler implicitement l’ordre de mise à jour des routeurs, à travers une modification progressive du poids d’un sous-ensemble de liens. Par exemple, l’augmentation du poids d’un lien aura pour effet de forcer les routeurs les plus éloignés de ce composant à se mettre à jour avant les routeurs plus proches. En adaptant finement l’amplitude de tels changements, il est alors possible de répartir la mise à jour de routeurs potentiellement impliqués dans une boucle sur plusieurs étapes. Cette opération peut ensuite être répétée jusqu’à ce que le composant ne soit plus utilisé pour acheminer des données dans le réseau, permettant un retrait sans impact sur le routage. / The use of real time media or mission critical applications over IP networks is making strong pressure on service providers to operate disruption free networks. However, after any topological change, link-state Interior Gateway Protocols (IGPs), such as IS-IS or OSPF, enter a convergence phase during which transient forwarding loops may occur. Such loops increase the network latency and cause packet losses for several seconds. In this thesis, we propose and evaluate innovative solutions to prevent these perturbations in case a planned modification on a link or a router. Our approach only relies on core functionalities of link-state routing protocols, thus being incrementally deployable in any network. Intuitively, it consists in implicitly controlling the routers update order through successive IGP weight reconfigurations on a subset of links. For example, progressively increasing the weight of a link forces farthest routers to update their routes first, before closest ones. Hence, finely tuning such changes may allow to spread the update of routers potentially implied in a loop across multiple steps. This operation can be repeated until the component to be removed is no longer used to forward traffic in the network, thus allowing its removal with no impact on the routing decisions.

Στη διπλωματική εργασία προς παρουσίαση, πραγματευόμαστε ένα νέο είδος γραφημάτων, τα χρονικά γραφήματα, και διάφορες παραλλαγές τους. Ένα χρονικό γράφημα είναι μια διατεταγμενη τριάδα G={V,E,L}, όπου V ένα μη κενό πεπερασμένο σύνολο που καλείται σύνολο κορυφών, E ένα σύνολο m στοιχείων, καθένα από τα οποία είναι δισύνολο στοιχείων του V (καλείται σύνολο ακμών), και L= {L_e, για κάθε e στοιχείο του E} = {L_e_1, L_e_2, ..., L_e_m}, όπου L_e_i, i = 1,..., m, σύνολο θετικών ακεραίων τιμών που αντιστοιχίζονται στην ακμή e_i του συνόλου E (καλείται ανάθεση χρονικών ετικετών ή απλώς ανάθεση). Οι τιμές που αντιστοιχίζονται σε κάθε ακμή του γραφήματος καλούνται χρονικές ετικέτες της ακμής και δηλώνουν τις χρονικές στιγμές, κατά τις οποίες έχουμε τη δυνατότητα να τη διασχίσουμε (από το ένα της άκρο προς το άλλο). Για να αντιληφθεί κανείς το ενδιαφέρον των χρονικών γραφημάτων, μπορεί να σκεφτεί τη δυνατότητα εφαρμογής τους στην καθημερινότητα. Για παράδειγμα, οι χρονικές ετικέτες που ανατίθενται σε μία ακμή ενός κατευθυνόμενου χρονικού γραφήματος μπορούν να παραλληλιστούν με τις ώρες, στις οποίες γίνονται αναχωρήσεις αεροπλάνων από μία πόλη προς μια άλλη. Έτσι, η μελέτη των χρονικών γραφημάτων θα μπορούσε να συμβάλει στην οργάνωση των πτήσεων ενός αεροδρομίου. Ένα χρονικό μονοπάτι (ή «ταξίδι») σε ένα χρονικό γράφημα είναι ένα μονοπάτι, στις ακμές του οποίου μπορούμε να βρούμε αυστηρά αύξουσα σειρά χρονικών ετικετών. Στην εργασία, μεταξύ άλλων, γίνεται μελέτη της συνδετικότητας στα χρονικά γραφήματα, καθώς και κατασκευή και μελέτη αλγορίθμων εύρεσης χρονικών μονοπατιών («ταξιδίων») που φθάνουν το δυνατόν συντομότερα στον προορισμό τους (τελική κορυφή μονοπατιού). Επιπλέον, μελετώνται στατιστικά τα Χρονικά Γραφήματα, με επικέντρωση στο αναμενόμενο πλήθος χρονικών μονοπατιών σε ένα γράφημα, καθώς και στη Χρονική Διάμετρο ενός γραφήματος, όπως αυτή ορίζεται στην εργασία. / In the thesis, we are dealing with a new type of graphs,called Temporal Graphs, and several variants. A temporal graph is an ordered triplet G={V,E,L}, where V stands for a nonempty finite set (called set of vertices), E stands for a set of m elements, each of which are 2-element subsets of V (called set of edges), and L= {L_e, for all e in E} = {L_e_1, L_e_2, ..., L_e_m}, where L_e_i, i = 1, ..., m, is a set of positive integers mapped to edge e_i in E (called assignment of time labels or simply assignment). The values assigned to each edge of the graph are called time labels of the edge and indicate the times at which we can cross it (from one end to the other). In order to understand the interest of temporal graphs, one may think their applicability to everyday life. For example, the time labels assigned to an edge of a directed temporal graph can be paralleled to the flight departure times from one city to another. Therefore, the study of temporal graphs could contribute to the organization of flights at an airport. A temporal path (or «journey») in a temporal graph is a path, on the edges of which we can find strictly ascending time labels. In the thesis, among others, we study the connectivity of temporal graphs and we construct and study several algorithms that find temporal paths which arrive the soonest possible at their destination (final vertice of the path). Furthermore, we examine temporal graphs statistically, focusing on the expected number of temporal paths in a graph as well as in the Temporal Diameter of a graph, also defined in the thesis.

Les systèmes robotiques et autonomes ne cessent d’évoluer et deviennent de plus en plus impliqués dans les missions à coût considérable et/ou dans les milieux humains. Par conséquent, les simulations et campagnes de tests ne sont plus adaptées à la problématique de sûreté et fiabilité des systèmes robotiques et autonomes compte tenu (i) du caractère sérieux des défaillances éventuelles dans les contextes susmentionnés (un dommage à un robot très coûteux ou plus dramatiquement une atteinte aux vies humaines) et (ii) de la nature non exhaustive de ces techniques (les tests et simulations peuvent toujours passer à côté d’un scénario d’exécution catastrophique.Les méthodes formelles, quant à elles, peinent à s’imposer dans le domaine de la robotique autonome, notamment au niveau fonctionnel des robots, i.e. les composants logiciels interagissant directement avec les capteurs et les actionneurs. Elle est due à plusieurs facteurs. D’abord, les composants fonctionnels reflètent un degré de complexité conséquent, ce qui mène souvent à une explosion combinatoire de l’espace d’états atteignables (comme l’exploration se veut exhaustive). En outre, les composants fonctionnels sont décrits à travers des languages et frameworks informels (ROS, GenoM, etc.). Leurs spécifications doivent alors être traduites en des modèles formels avant de pouvoir y appliquer les méthodes formelles associées. Ceci est souvent pénible, lent, exposé à des erreurs, et non automatique, ce qui implique un investissement dans le temps aux limites de la rentabilité. Nous proposons, dans cette thèse, de connecter GenoM3, un framework de développement et déploiement de composants fonctionnels robotiques, à des langages formels et leurs outils de vérification respectifs. Cette connexion se veut automatique: nous développons des templates en mesure de traduire n’importe quelle spécification de GenoM3 en langages formels. Ceci passe par une formalisation de GenoM3: une sémantique formelle opérationnelle est donnée au langage. Une traduction à partir de cette sémantique est réalisée vers des langages formels et prouvée correcte par bisimulation. Nous comparons de différents langages cibles, formalismes et techniques et tirerons les conclusions de cette comparaison. La modélisation se veut aussi, et surtout, efficace. Un modèle correct n’est pas forcément utile. En effet, le passage à l’échelle est particulièrement important.Cette thèse porte donc sur l'applicabilité des méthodes formelles aux compo-sants fonctionnels des systèmes robotiques et autonomes. Le but est d'aller vers des robots autonomes plus sûrs avec un comportement plus connu et prévisible. Cela passe par la mise en place d'un mécanisme de génération automatique de modèles formels à partir de modules fonctionnels de sys-tèmes robotiques et autonomes. Les langages et outils cibles sont Fiacre/TINA et UPPAAL (model checking), UPPAAL-SMC (statistical model checking), BIP/RTD-Finder (SAT solving), et BIP/Engine (enforcement de propriétés en ligne). Les modèles générés sont exploités pour vérifier des propriétés quali-tatives ou temps-réel, souvent critiques pour les systèmes robotiques et auto-nomes considérés. Parmi ces propriétés, on peut citer, à titre d'exemple, l'ordonnançabilité des tâches périodiques, la réactivité des tâches spora-diques, l'absence d’interblocages, la vivacité conditionnée (un évènement tou-jours finit par suivre un autre), la vivacité conditionnée bornée (un évène-ment toujours suit un autre dans un intervalle de temps borné), l'accessibilité (des états “indésirables” ne sont jamais atteints), etc.La thèse propose éga-lement une analyse du feedback expérimental afin de guider les ingénieurs à exploiter ces méthodes et techniques de vérification efficacement sur les mo-dèles automatiquement générés. / The goal of this thesis is to add to the efforts toward the long-sought objective of secure and safe robots with predictable and a priori known behavior. For the reasons given above, formal methods are used to model and verify crucial properties, with a focus on the functional level of robotic systems. The approach relies on automatic generation of formal models targeting several frameworks. For this, we give operational semantics to a robotic framework, then several mathematically proven translations are derived from such semantics. These translations are then automatized so any robotic functional layer specification can be translated automatically and promptly to various frameworks/languages. Thus, we provide a mathematically correct mapping from functional components to verifiable models. The obtained models are used to formulate and verify crucial properties (see examples above) on real-world complex robotic and autonomous systems. This thesis provides also a valuable feedback on the applicability of formal frameworks on real-world, complex systems and experience-based guidelines on the efficient use of formal-model automatic generators. In this context, efficiency relates to, for instance, how to use the different model checking tools optimally depending on the properties to verify, what to do when the models do not scale with model checking (e.g. the advantages and drawbacks of statistical model checking and runtime verification and when to use the former or the latter depending on the type of properties and the order of magnitude of timing constraints).