Academic literature on the topic 'Graphe d'intervalles'

La largeur linéaire et la largeur arborescente ont été introduites par Robertson et Seymour dans leurs travaux sur les mineurs de graphes. De manière informelle, la largeur linéaire (resp. la largeur arborescente) d'un graphe mesure l'écart entre ce graphe et la classe des chaînes (des arbres). Les deux paramètres se sont révélés très puissants de point de vue algorithmique, car de nombreux problèmes NP-difficiles deviennent polynomiaux lorsque l'on se restreint à des classes de graphes de largeur linéaire ou de largeur arborescente bornée. Etant donné un graphe G=(V,E) quelconque, un graphe d'intervalles H=(V,F) contenant G est appelé complétion d'intervalles de G. Calculer la largeur linéaire de G revient à trouver une complétion d'intervalles H, tout en minimisant la clique maximum de H. Le problème étant NP-difficile, nous calculerons des complétions d'intervalles minimales, où l'on demande seulement que l'ensemble d'arêtes rajoutées F\E soit minimal par inclusion parmi toutes les complétions possibles. Une approche similaire, à travers les triangulations minimales, est fortement utilisée pour comprendre et calculer la largeur arborescente. Ce mémoire présente nos résultats sur les complétions d'intervalles minimales. Nous donnons trois algorithmes calculant une complétion d'intervalles minimale, basés sur des approches différentes. Nous présentons également un algorithme calculant une complétion d'intervalles propres minimale. Enfin, nous montrons que la largeur linéaire des graphes d'intervalles circulaires peut être calculée en temps polynomial.

Situee dans le prolongement des approches algebriques et topologiques des problemes de temps, cette these propose une alternative aux methodes de representation et de propagation de contraintes concernant les intervalles d'un espace lineaire. Le point determinant reside dans le choix des intervalles comme unique entite temporelle et de la relation meet comme unique moyen de representation du systeme de contraintes: on obtient ainsi un graphe classique. Nous decrivons une methode de construction d'un tel graphe a partir d'informations de haut niveau. Les proprietes essentielles de la relation meet (z-propriete, 2-absorption) nous permettent de construire un algorithme de deduction, qui consiste a fermer le graphe vis-a-vis de ces deux proprietes. Nous montrons aussi comment et quand identifier les redondances et les incoherences dans un graphe de meet. A ce stade le noyau du modele est stabilise dans ces grandes lignes, il restait a l'evaluer. Nous apportons des elements de reponse sur deux plans: celui de la taille des donnees et de la complexite des traitements, d'une part, celui de la robustesse du modele a travers son adaptation aux intervalles ponctuels, d'autre part

On dit d'un sous-ensemble de NP qu'il présente une dichotomie s'il contient des problèmes qui sont soit résolubles en temps polynomial (dans Ptime), soit difficiles (NP-complets). La classe des problèmes de satisfaction de contraintes (CSP) finis est un sous-ensemble bien connu de NP qui présente une telle dichotomie. La classe de complexité NP n'a pas de dichotomie à moins que P = NP. Pour ces deux classes, il existe des logiques qui leur sont associées. -- NP est capturé par la logique Existentielle du second ordre (ESO) par le théorème de Fagin, c'est-à-dire qu'un problème est dans NP si et seulement s'il est exprimable par une formule ESO.-- CSP est un sous-ensemble de la logique de Feder et Vardi, le fragment monotone, monadique et sans inégalités de SNP, lui-même un fragment syntaxique de ESO (MMSNP); et, pour chaque formule de MMSNP, il existe un problème CSP équivalent via des réductions polynomiales.Ceci implique que la logique ESO, tout comme NP, n'a pas de dichotomie, à contraster avec le fait que MMSNP a une dichotomie tout comme CSP. L'objectif principal de cette thèse est d'étudier les propriétés de dichotomie de sous-ensembles de NP qui contiennent strictement CSP ou MMSNP.Feder et Vardi ont prouvé que si nous omettons une des trois propriétés qui définissent MMSNP, à savoir être monotone, monadique ou omettre les inégalités, alors la logique résultante n'a pas de dichotomie. Comme leurs preuves restent parfois sommaires, nous revisitons ces résultats et fournissons des preuves détaillées. Le fragment guardé et monotone de SNP (GMSNP) est une extension connue de MMSNP qui est obtenue en relâchant la restriction "monadique" de MMSNP. Nous définissons de manière similaire une nouvelle logique appelée MMSNP avec des inégalités gardées, en relâchant la restriction d'être "sans inégalités". Nous prouvons qu'elle est strictement plus expressive que MMSNP et qu'elle possède également une dichotomie.Il existe une logique MMSNP₂ qui étend MMSNP de la même manière que MSO₂ étend la logique monadique du second ordre (MSO). On sait que MMSNP₂ est un fragment de GMSNP et que ces deux classes ont toutes deux une dichotomie ou n'en ont pas. Nous revisitons ce résultat et le renforçons en prouvant que, en ce qui concerne le fait d'avoir une dichotomie, sans perte de généralité, on peut considérer seulement les problèmes MMSNP₂ sur des signatures à un élément, au lieu des problèmes GMSNP sur des signatures finies arbitraires.Nous cherchons à prouver l'existence d'une dichotomie pour les MMSNP₂ en construisant en temps polynomial, pour tout problème MMSNP₂, un problème MMSNP équivalent. Nous rencontrons quelques obstacles pour construire une telle équivalence. Cependant, si nous permettons aux formules MMSNP d'être composées d'un nombre dénombrable de conjonctions négatives, nous prouvons qu'une telle équivalence existe. De plus, la formule MMSNP infinie correspondante a la propriété d'être "régulière". Cette propriété de régularité signifie que, dans un certain sens, cette formule est essentiellement finie. Il est connu que les problèmes MMSNP réguliers peuvent être exprimés par CSP sur des modèles oméga-catégoriques. De plus, il existe une caractérisation de la dichotomie algébrique pour les CSP oméga-catégoriques qui décrivent des problèmes MMSNP. Si l'on parvient à étendre cette caractérisation algébrique sur les problèmes réguliers MMSNP, alors notre résultat fournirait une dichotomie algébrique pour MMSNP₂. (...)
A subset of NP is said to have a dichotomy if it contains problem that are either solvable in P-time or NP-complete. The class of finite Constraint Satisfaction Problems (CSP) is a well-known subset of NP that follows such a dichotomy. The complexity class NP does not have a dichotomy unless P = NP. For both of these classes there exist logics that are associated with them. -- NP is captured by Existential Second-Order (ESO) logic by Fagin's theorem, i.e., a problem is in NP if and only if it is expressible by an ESO sentence.-- CSP is a subset of Feder and Vardi's logic, Monotone Monadic Strict NP without inequalities (MMSNP), and for every MMSNP sentence there exists a P-time equivalent CSP problem. This implies that ESO does not have a dichotomy as well as NP, and that MMSNP has a dichotomy as well as CSP. The main objective of this thesis is to study subsets of NP that strictly contain CSP or MMSNP with respect to the dichotomy existence.Feder and Vardi proved that if we omit one of the three properties that define MMSNP, namely being monotone, monadic or omitting inequalities, then the resulting logic does not have a dichotomy. As their proofs remain sketchy at times, we revisit these results and provide detailed proofs. Guarded Monotone Strict NP (GMSNP) is a known extension of MMSNP that is obtained by relaxing the "monadic" restriction of MMSNP. We define similarly a new logic that is called MMSNP with Guarded inequalities, relaxing the restriction of being "without inequalities". We prove that it is strictly more expressive than MMSNP and that it also has a dichotomy.There is a logic MMSNP₂ that extends MMSNP in the same way as MSO₂ extends Monadic Second-Order (MSO) logic. It is known that MMSNP₂ is a fragment of GMSNP and that these two classes either both have a dichotomy or both have not. We revisit this result and strengthen it by proving that, with respect to having a dichotomy, without loss of generality, one can consider only MMSNP₂ problems over one-element signatures, instead of GMSNP problems over arbitrary finite signatures.We seek to prove the existence of a dichotomy for MMSNP₂ by finding, for every MMSNP₂ problem, a P-time equivalent MMSNP problem. We face some obstacles to build such an equivalence. However, if we allow MMSNP sentences to consist of countably many negated conjuncts, then we prove that such an equivalence exists. Moreover, the corresponding infinite MMSNP sentence has a property of being "regular". This regular property means that, in some sense, this sentence is still finite. It is known that regular MMSNP problems can be expressed by CSP on omega-categorical templates. Also, there is an algebraic dichotomy characterisation for omega-categorical CSPs that describe MMSNP problems. If one manages to extend this algebraic characterisation onto regular MMSNP, then our result would provide an algebraic dichotomy for MMSNP₂.Another potential way to prove the existence of a dichotomy for MMSNP₂ is to mimic the proof of Feder and Vardi for MMSNP. That is, by finding a P-time equivalent CSP problem. The most difficult part there is to reduce a given input structure to a structure of sufficiently large girth. For MMSNP and CSP, it is done using expanders, i.e., structures, where the distribution of tuples is close to a uniform distribution. We study this approach with respect to MMSNP₂ and point out the main obstacles. (...)

Cette thèse est consacrée à l'évaluation de requêtes logiques du point de vue de l'énumération. Nous étudions quatre classes de requêtes. En premier lieu, nous nous intéressons aux formules conjonctives acycliques avec inégalités pour lesquelles nous améliorons un résultat de Papadimitriou et Yannakakis en montrant que de telles requêtes logiques peuvent être évaluées à délai linéaire en la taille de la structure. Nous exhibons ensuite la sous-classe des formules connexe-acycliques pour lesquelles l'évaluation de requêtes s'effectue à délai constant après prétraitement linéaire. Nous montrons que cette classe est maximale pour ce résultat dans le sens suivant: si le produit de matrices booléennes ne peut pas être calculé en temps linéaire alors toute requête conjonctive acyclique est évaluable à délai constant après prétra itement linéaire si et seulement si elle est connexe-acyclique. En second lieu, nous démontrons que toute requête MSO sur une classe de structures de largeur arborescente bornée peut être évaluée à délai linéaire en la taille de chaque solution produite après un prétraitement linéaire en la taille de la structure. En troisième lieu, nous montrons que, pour chaque requête en logique du premier ordre sur des structures de degré borné, il est possible de trouver en temps constant la j-ème solution dans un certain ordre après un prétraitement linéraire. Enfin, nous établissons que les graphes d'intervalles unitaires ont une largeur de clique localement bornée. D'où nous déduisons que tout énoncé du premier ordre sur ces graphes est décidable en temps linéaire; là encore, nous démontrons une certaine maximalité de ce résultat.

Ce travail de thèse traite du maintien dynamique de représentations géométriques de graphes. Le manuscrit met en avant des connexions fortes entre trois types de représentation de graphes : les décompositions de graphes, les modèles géométriques et les représentations arborescentes à degrés de liberté (PQ-arbres, PC-arbres et autres structures du même type). De nouvelles relations entre ces objets sont mises en évidence et d'autres déjà connues sont approfondies. Notamment, il est établi une équivalence mathématique et algorithmique entre la décomposition modulaire des graphes d'intervalles et le PQ-arbre de leurs cliques maximales.

Les connexions entre les trois types de représentation précités sont exploitées pour la conception d'algorithmes de reconnaissance entièrement dynamiques pour les cographes orientés, les graphes de permutation et les graphes d'intervalles. Pour les cographes orientés, l'algorithme présenté est de complexité optimale, il traite les modifications de sommet en temps O(d), où d est le degré du sommet en question, et les modifications d'arête en temps constant. Les algorithmes pour les graphes de permutation et les graphes d'intervalles ont la même complexité : les modifications d'arête et de sommet sont traitées en temps O(n), où n est le nombre de sommets du graphe. Une des contributions du mémoire est de mettre en lumière des similarités très fortes entre les opérations d'ajout d'un sommet dans un graphe de permutation et dans un graphe d'intervalles.
L'approche mise en oeuvre dans ce mémoire est assez générale pour laisser entrevoir les mêmes possibilités algorithmiques pour d'autres classes de graphes définies géométriquement.

Dans cette thèse, nous nous intéressons à deux types de décompositions des graphes introduits par Robertson et Seymour: les décompositions arborescentes et les décompositions en branches. À ces décompositions sont associés deux paramètres des graphes: la largeur arborescente et la largeur de branches. Nous montrons que ces deux décompositions peuvent être vues comme issues d'une même structure combinatoire; les deux paramètres mentionné ci-dessus sont égaux aux valeurs minimales de deux paramètres de cette structure commune. En poussant plus avant cette analogie, nous montrons comment adapter une technique de calcul de la largeur arborescente au calcul de la largeur de branches. Ceci nous permet de calculer la largeur de branches des graphes de nombre astéroïde borné ayant un nombre polynômial de séparateurs minimaux et celle des graphes d-trapézoïdes circulaires. Ce parallèle nous permet aussi d'adapter certains résultats structurels sur les décompositions en branches aux décompositions arborescentes. Dans le cas des graphes planaires, nous interprétons ces propriétés à l'aide d'outils topologiques. De cette façon, nous donnons une démonstration simple d'un théorème de dualité reliant la largeur arborescente d'un graphe planaire et celle de son dual. Ces outils nous permettent aussi d'énumérer de façon efficace les séparateurs minimaux des graphes planaires.

Le problème de placement sur deux dimensions consiste à décider s'il existe un rangement d'objets rectangulaires dans une boîte donnée. C'est un problème combinatoire difficile (à la complexité du respect des capacités s'ajoute celle du positionnement des objets). Nous considérons les variantes sans rotation des objets et avec ou sans optimisation de la valeur des objets placés. Nous menons une étude exploratoire des méthodologies qui peuvent être développées à l'interface de la programmation mathématique, de l'optimisation combinatoire et de la théorie des graphes. Nous comparons les formulations de la littérature et en proposons de nouvelles. Nous développons et testons deux approches de résolution innovantes. L'une est basée sur la décomposition de Dantzig-Wolfe (avec un branchement sur les contraintes disjonctives de non recouvrement des objets). L'autre constitue en une approche combinatoire basée sur diverses caractérisations des graphes d'intervalles (modélisant le chevauchement des objets selon chaque axe).

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identifiant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.