To see the other types of publications on this topic, follow the link: Graphe biparti.
Dissertations / Theses on the topic 'Graphe biparti'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graphe biparti.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Topart, Hélène. "Etude d’une nouvelle classe de graphes : les graphes hypotriangulés." Thesis, Paris, CNAM, 2011. http://www.theses.fr/2011CNAM0776/document.
Full textAbstract:
Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphesIn this thesis, we define a new class of graphs : the hypochordal graphs. These graphs satisfy that for any path of length two, there exists a chord or another path of length two between its two endpoints. This class can represent robust networks. Indeed, we show that in such graphs, in the case of an edge or a vertex deletion, the distance beween any pair of nonadjacent vertices remains unchanged. Then, we study several properties for this class of graphs. Especially, after introducing a family of specific partitions, we show the relations between some of these partitions and hypochordality. Moreover, thanks to these partitions, we characterise minimum hypochordal graph, that are, among connected hypochordal graphs, those that minimise the number of edges for a given number of vertices. In a second part, we study the complexity, for hypochordal graphs, of problems that are NP-hard in the general case. We first show that the classical problems of hamiltonian cycle, colouring, maximum clique and maximum stable set remain NP-hard for this class of graphs. Then, we analyse graph modification problems : deciding the minimal number of edges to add or delete from a graph, in order to obtain an hypochordal graph. We study the complexity of these problems for sevaral classes of graphs
2
Topart, Hélène. "Etude d'une nouvelle classe de graphes : les graphes hypotriangulés." Phd thesis, Conservatoire national des arts et metiers - CNAM, 2011. http://tel.archives-ouvertes.fr/tel-00686960.
Full textAbstract:
Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes.
3
Barkaoui, Kamel. "Contribution aux methodes d'analyse des reseaux de petri par la theorie des graphes." Paris 6, 1988. http://www.theses.fr/1988PA066041.
Full textAbstract:
On introduit la notion de composante preconservative minimale (theoreme). On fournit une nouvelle caracterisation de la minimalite des verrous et des trappes. On etablit un lemme permettant d'etendre le domaine de validite de la propriete communer (condition suffisante de vivacite)
4
Cotté, Grégoire. "d-extensibles, d-bloqueurs et d-transversaux de problèmes d'optimisation combinatoire." Thesis, Paris, CNAM, 2016. http://www.theses.fr/2016CNAM1037/document.
Full textAbstract:
Dans cette thèse, nous étudions trois catégories de problèmes : les d-extensibles, les d-bloqueurs et les d-transversaux.Les d-extensibles de stables optimaux sont des ensembles de sommets d'un graphe G tels que tout stable de cardinal d du sous-graphe induit par un d-extensible peut être étendu à un stable optimal de G à l'aide de sommets qui n'appartiennent pas au d-extensible. Nous étudions les d-extensibles de cardinal maximal de stables dans les graphes bipartis. Nous démontrons quelques propriétés structurelles puis nous déterminons une borne inférieure du cardinal maximal d'un d-extensible. Nous étudions quelques classes de graphes dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial. Nous nous intéressons ensuite aux d-extensibles de stables dans les arbres. Nous prouvons plusieurs propriétés structurelles, déterminons une autre borne inférieure du cardinal maximal d'un d-extensible et étudions quelques classes d'arbres dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial.Les d-bloqueurs de stables sont des ensembles de sommets d'un graphe G tels que, si on retire les sommets d'un d-bloqueur, le cardinal maximal d'un stable du graphe induit par les sommets restants est inférieur d'au moins d au cardinal maximal d'un stable du graphe initial. Nous nous intéressons ici aux d-bloqueurs de coût minimal de stables dans les arbres. Après avoir prouvé une caractérisation des d-bloqueurs de stables dans les arbres, nous démontrons que déterminer un d-bloqueur de coût minimal de stable est un problème polynomial dans une classe d'arbres particulière.Soit Pi un problème d'optimisation sur un ensemble d'éléments fini. Un d-transversal de Pi est un ensembles d'éléments tel que l'intersection entre le d-transversal et toute solution optimale au problème Pi est de cardinal supérieur égal à d. Nous proposons ici une approche de génération de contraintes pour déterminer des d-transversaux de cardinal maximal de problèmes modélisés par des programmes mathématiques en variables binaires. Nous étudions deux variantes de cette approche que nous testons sur des instances de graphes générés aléatoirement pour déterminer des d-transversaux de stables optimaux et des d-transversaux de couplages optimauxIn this thesis, we study three types of problems : the d-extensibles sets, the d-blockers and the d-transversals.In a graph G, a d-extensible set of maximum independent sets is a subset of vertices of G such that every stable set of cardinality d in the subgraph restricted to the d-extensible set can be extented to a maximum stable set of G using only vertices that do not belong to the d-extensible set. We study d-extensible sets of mxaimum cardinality of stable sets in bipartite graphs. We show some structural properties and we determine a lower bound of the maximum cardinality of a d-extensible set. We consider some classes of graph where finding an optimum d-extensible set can be done in polynomial time. Then, we study the d-extensibles sets of stable sets in trees. We prove some properties on the structures of the d-extensibles sets and we determine another lower bound of the maximum cardinality of a d-extensible set. Finaly, we study somme classes of tree where a d-extensible sets of maximum cardinality can be done in polynomial time.In a graph G, a d-blocker is a subset of vertices such that, if removed, a maximum stable set of the resulting subgraph is of cardinality at most the cardinality of a maximum stable set of G minus d. We study d-blocker of minimal cost of stable sets in tree.We prove a caracterisation of d-blockers in tree and we study a particular classe of trees where computing a d-blocker of minimal cost of stable sets can be done in polynomial time.Let Pi be an optimisation problem on a finite set of elements. A d-transversal of Pi is a subset of elements such that the intersection between the d-transversal and every optimal solution of Pi contains at lest d elements. We propose an approach to compute d-transversal of any optimisation problem modelised by mathematical program with binary variables. We use a contraints generation approach. We compare two variations of this approach on randomly generated graph by computing d-transversals of stables sets and d-transversals of matching
5
Viana, do Espírito Santo Ilísio. "Inspection automatisée d’assemblages mécaniques aéronautiques par vision artificielle : une approche exploitant le modèle CAO." Thesis, Ecole nationale des Mines d'Albi-Carmaux, 2016. http://www.theses.fr/2016EMAC0022/document.
Full textAbstract:
Les travaux présentés dans ce manuscrit s’inscrivent dans le contexte de l’inspection automatisée d’assemblages mécaniques aéronautiques par vision artificielle. Il s’agit de décider si l’assemblage mécanique a été correctement réalisé (assemblage conforme). Les travaux ont été menés dans le cadre de deux projets industriels. Le projet CAAMVis d’une part, dans lequel le capteur d’inspection est constitué d’une double tête stéréoscopique portée par un robot, le projet Lynx© d’autre part, dans lequel le capteur d’inspection est une caméra Pan/Tilt/Zoom (vision monoculaire). Ces deux projets ont pour point commun la volonté d’exploiter au mieux le modèle CAO de l’assemblage (qui fournit l’état de référence souhaité) dans la tâche d’inspection qui est basée sur l’analyse de l’image ou des images 2D fournies par le capteur. La méthode développée consiste à comparer une image 2D acquise par le capteur (désignée par « image réelle ») avec une image 2D synthétique, générée à partir du modèle CAO. Les images réelles et synthétiques sont segmentées puis décomposées en un ensemble de primitives 2D. Ces primitives sont ensuite appariées, en exploitant des concepts de la théorie de graphes, notamment l’utilisation d’un graphe biparti pour s’assurer du respect de la contrainte d’unicité dans le processus d’appariement. Le résultat de l’appariement permet de statuer sur la conformité ou la non-conformité de l’assemblage. L’approche proposée a été validée à la fois sur des données de simulation et sur des données réelles acquises dans le cadre des projets sus-citésThe work presented in this manuscript deals with automated inspection of aeronautical mechanical parts using computer vision. The goal is to decide whether a mechanical assembly has been assembled correctly i.e. if it is compliant with the specifications. This work was conducted within two industrial projects. On one hand the CAAMVis project, in which the inspection sensor consists of a dual stereoscopic head (stereovision) carried by a robot, on the other hand the Lynx© project, in which the inspection sensor is a single Pan/Tilt/Zoom camera (monocular vision). These two projects share the common objective of exploiting as much as possible the CAD model of the assembly (which provides the desired reference state) in the inspection task which is based on the analysis of the 2D images provided by the sensor. The proposed method consists in comparing a 2D image acquired by the sensor (referred to as "real image") with a synthetic 2D image generated from the CAD model. The real and synthetic images are segmented and then decomposed into a set of 2D primitives. These primitives are then matched by exploiting concepts from the graph theory, namely the use of a bipartite graph to guarantee the respect of the uniqueness constraint required in such a matching process. The matching result allows to decide whether the assembly has been assembled correctly or not. The proposed approach was validated on both simulation data and real data acquired within the above-mentioned projects
6
Tackx, Raphaël. "Analyse de la structure communautaire des réseaux bipartis." Electronic Thesis or Diss., Sorbonne université, 2018. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2018SORUS550.pdf.
Full textAbstract:
Il existe dans le monde réel un nombre important de réseaux qui apparaissent naturellement, on les retrouve un peu partout, dans de nombreuses disciplines, par exemple en informatique avec les réseaux de routeurs, les réseaux de satellites, les réseaux de pages Web, en biologie avec les réseaux des neurones, en écologie avec les réseaux d’interactions biologiques, en linguistiques avec les réseaux de synonymes, en droit avec les réseaux de décisions juridiques, en économie avec les réseaux interbancaires, en sciences humaines avec les réseaux sociaux. De manière générale, un réseau reflète les interactions entre les nombreuses entités d’un système. Ces interactions peuvent être de différentes natures, un lien social ou un lien d’amitié dans un réseau social constitué de personnes, un câble dans un réseau de routeurs, une réaction chimique dans un réseau biologique de protéines, un hyperlien dans un réseau de pages Web, etc. Plus encore, la rapide démocratisation du numérique dans nos sociétés, avec Internet notamment, a pour conséquence de produire de nouveaux systèmes qui peuvent être représentés sous forme de réseaux. Finalement, tous ces réseaux présentent des particularités bien spécifiques : ils sont issus de contextes pratiques, ils sont le plus souvent de grande taille (on retrouve quelques fois des réseaux constitués de plusieurs milliards de nœuds et de liens, contenant donc une grande quantité d’information), ils présentent des propriétés statistiques communes. À cet égard, ils sont regroupés sous l’appellation de réseaux réels, graphes de terrain ou encore réseaux complexes. Aujourd'hui, la science des réseaux est un domaine de recherche à part entière dont l’enjeu principal est de parvenir à décrire et modéliser ces réseaux avec précision afin de révéler leurs caractéristiques générales et de mieux comprendre leurs mécanismes. La plupart des travaux dans ce domaine utilisent le formalisme des graphes qui fournit un ensemble d’outils mathématiques particulièrement adaptés à l’analyse topologique et structurelle des réseaux. Il existe de nombreuses applications dans ce domaine, par exemple des applications concernant la propagation d’épidémie ou de virus informatique, la fragilité du réseau en cas de panne, sa résilience en cas d’attaque, l’étude de la dynamique pour prédire l’apparition de nouveaux liens, la recommandation, etc. L’un des problèmes complexes actuels, qui a beaucoup d’applications, est l’identification de la structure communautaire. La grande majorité des réseaux réels sont caractérisés par des niveaux d’organisation dans leur structure mésoscopique. Du fait de la faible densité globale des réseaux réels couplée à la forte densité locale, on observe la présence de groupes de nœuds fortement liés entre eux et plus faiblement liés avec le reste du réseau, que l’on appelle communautés. Ces structures ont également du sens dans le réseau lui-même, par exemple les communautés d’un réseau social peuvent correspondre à des groupes sociaux (amis, familles, etc.), les communautés d’un réseau de protéines peuvent traduire des réponses fonctionnelles, elles peuvent correspondre à des sujets similaires dans un réseau de pages Web, pour donner quelques exemples [...]In the real world, numerous networks appear naturally, they are everywhere, in many disciplines, for example in computer science with router networks, satellite networks, webpage networks, in biology with neural networks, in ecology with biological interaction networks, in linguistic with synonym networks, in law with legal decision networks, in economy with interbank networks, in social sciences and humanities with social networks. Generally, a network reflects the interactions between many entities of a system. These interactions have different sources, a social link or a friendship link in a social network, a cable in a router network, a chemical reaction in a protein-protein interaction network, a hyperlink in a webpage network. Furthermore, the rapid democratization of digital technology in our societies, with internet in particular, leads to create new systems which can be seen as networks. Finally, all these networks depict very specific features : they come from pratical contexts, most of the time they are big (they may be comprised of several billion of nodes and links, containing a large amount of information), they share statistical properties. In this regard, they are called real-world networks or complex networks. Nowaday, network science is a research area in its own right focusing on describing and modeling these networks in order to reveal their main features and improve our understanding of their mecanisms. Most of the works in this area use graphs formalism which provides a set of mathematical tools well suited for analyzing the topology of these networks. It exists many applications, for instance applications in spread of epidemy or computer viruses, weakness of networks in case of a breakdown, attack resilience, study for link prediction, recommandation, etc. One of the major issue is the identification of community structure. The large majority of real-world networks depicts several levels of organization in their structure. Because of there is a weak global density coupled with a strong local density, we observe that nodes are usually organized into groups, called communities, which are more internally connected than they are to the rest of the network. Moreover, these structures have a meaning in the network itself, for example communities of a social network may correspond to social groups (friends, families, etc.), communities of a protein-protein network may translate fonctions of a cell, communities may be also related to similar subjects in a webpage network [...]
7
Al-Iedani, Najat Hameed Qasim. "Contribution à la résolution des problèmes d'optimisation combinatoire : cas du problème des k-clusters dans un graphe biparti et du problème de sac à dos quadratique." Thesis, Amiens, 2017. http://www.theses.fr/2017AMIE0035/document.
Full textAbstract:
Les problèmes d'optimisation combinatoire sont d'un grand intérêt à la fois pour le monde scientifique et le monde industriel. Les enjeux scientifiques, économiques, environnementaux et sociaux sont très nombreux et très importants. C'est pour cela que la communauté scientifique mondiale recherche depuis longtemps des méthodes de modélisation, de simplification et de résolution de ces problèmes. Parmi les problèmes combinatoires les plus connus se trouvent les problèmes de sac à dos et les problèmes liés aux décompositions des graphes. Nous nous sommes intéressés dans cette thèse à deux problèmes importants : - Le problème de regroupement dans un graphe biparti ; - Le problème de sac à dos quadratique. Le problème de regroupement dans un graphe biparti a de nombreuses applications dans le domaine des télécommunications. Il a également un grand intérêt théorique dans la modélisation, la décomposition et la résolution de plusieurs autres problèmes combinatoires. Le problème de sac à dos quadratique a un large champ d'applications théoriques et pratiques dans nombreux domaines. Il est très utile dans la modélisation et la résolution dans un contexte de gestion des exclusions par exemple. Ces deux problèmes sont hautement combinatoires et sont très difficiles à résoudre d'une manière optimale d'un point de vue informatique. La résolution de ce type de problèmes peut se faire de deux manières : - La résolution optimale, dite également exacte, qui s’appuie sur des modélisations et des méthodes mathématiques puissantes dont l'objectif est d'identifier une solution optimale du problème traité. - La résolution approchée, qui s'appuie principalement sur des algorithmes capables d'approcher la solution optimale du problème traité mais sans garantir l'optimalité du résultat. Les méthodes approchées sont les plus utilisées par les informaticiens dans la résolution des problèmes issus de l'industrie et des services car ces méthodes permettent de résoudre des problèmes de grande taille et de répondre aux exigences fonctionnelles des donneurs d'ordres. Il existe aussi des méthodes de résolution hydrides qui peuvent combiner plusieurs méthodes de résolution approchées ou exactes et qui utilisent généralement des techniques de décomposition du problème initial pour permettre l'hybridation. C'est dans ce sens que s'oriente cette thèse. Nous proposons dans cette thèse deux méthodes de résolution hydriques : - Une première méthode hydride pour le problème de regroupement dans un graphe biparti qui combine une recherche par voisinage et un algorithme approché complémentaire. - Une deuxième méthode hybride pour le problème du sac à dos quadratique qui combine une recherche par voisinage et une méthode de réduction/fix-ation des variablesSince long time, the scientific world has sought for modeling, simplification and resolution of combinatorial optimization problems, because of these problems are most interest for the scientific and the industrial world and for the fields of operational research and computer science. The objective of this thesis is to solve the difficult combinatorial optimization problems using approximate resolution methods. And, we were interested on two important problems that find several significant applications in real world. The first part of the thesis is devoted to the K-clusters in a bipartite graph that has been applied in the field of telecommunication. The second part of the thesis addresses to the quadratic knapsack problem that can be used to accommodate a wide range of practical applications in numerous fields. On the other hand, these problems are highly combinatorial and difficult to solve from computational perspective. The K-clustering minimum bi-clique completion problem (K - CmBCP) was presented in the latest date and it is very significant in real world and it has been applied to several real applications such as aggregation of multicast sessions. Since telecommunication network cannot manage many multicast sessions at the same time, it is hence necessary to group the sessions into a limited number of clusters. We note that, the hybrid resolution methods can combine several approximate resolution methods or optimal resolution and approximate resolution and which generally use decomposition techniques of the initial problem to allow hybridation. In this thesis, we propose two hybrid resolution methods: A first hybrid method for the problem of K-clusters in a bipartite graph that combines a neighborhood search and a complementary algorithm. A second hybrid method for the quadratic knapsack problem which combines a large neighborhood search with a variable reduction / fixing method. The proposed algorithm is capable of solving the small, large and very large size instances of the QKP that cannot be solved by Cplex solver or by other methods
8
Thiant, Nicolas. "Constructions et reconstructions de pavages de dominos." Paris 6, 2006. http://www.theses.fr/2006PA066418.
Full textAbstract:
Cette thèse est une contribution à l'étude de problèmes de pavages par des dominos. Nous montrons comment élargir au cas d'un polyomino avec des trous la méthode de Thurston qui permet de paver en temps linéaire un polyomino sans trous par des dominos. Nous présentons un algorithme de pavage de complexité O(kn) pour un polyomino avec n cellules et k trous. En particulier, cet algorithme est linéaire pour un polyomino avec un nombre borné de trous. Nous exposons aussi l'état de nos recherches sur le problème du pavage de cardinalité maximale et, plus généralement, sur celui du couplage maximum dans un graphe biparti plan. Nous présentons un algorithme original de couplage dont la complexité reste encore à déterminer. Nous considérons enfin le problème de la reconstruction du pavage d'un rectangle à partir de ses projections orthogonales. Ce problème connu depuis une dizaine d'années restait non résolu. Nous présentons un algorithme polynomial qui réalise cette reconstruction.
9
Aïder, Méziane. "Réseaux d'interconnexion bipartis : colorations généralisées dans les graphes." Phd thesis, Grenoble 1, 1987. http://tel.archives-ouvertes.fr/tel-00325779.
Full textAbstract:
Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits
10
Ross, Christopher Jon. "Properties of Random Threshold and Bipartite Graphs." The Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1306296991.
Full text
11
Bowlin, Garry. "Maximum frustration of bipartite signed graphs." Diss., Online access via UMI:, 2009.
Find full text
12
Bush, Albert. "Two Problems on Bipartite Graphs." Digital Archive @ GSU, 2009. http://digitalarchive.gsu.edu/math_theses/72.
Full textAbstract:
Erdos proved the well-known result that every graph has a spanning, bipartite subgraph such that every vertex has degree at least half of its original degree. Bollobas and Scott conjectured that one can get a slightly weaker result if we require the subgraph to be not only spanning and bipartite, but also balanced. We prove this conjecture for graphs of maximum degree 3.
The majority of the paper however, will focus on graph tiling. Graph tiling (or sometimes referred to as graph packing) is where, given a graph H, we find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove an asymptotic minimum degree condition for an arbitrary bipartite graph G to be tiled by another arbitrary bipartite graph H. This proves a conjecture of Zhao and also implies an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.
13
Biyikoglu, Türker, Josef Leydold, and Peter F. Stadler. "Nodal Domain Theorems and Bipartite Subgraphs." Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, 2005. http://epub.wu.ac.at/626/1/document.pdf.
Full textAbstract:
The Discrete Nodal Domain Theorem states that an eigenfunction of the k-th largest eigenvalue of a generalized graph Laplacian has at most k (weak) nodal domains. We show that the number of strong nodal domains cannot exceed the size of a maximal induced bipartite subgraph and that this bound is sharp for generalized graph Laplacians. Similarly, the number of weak nodal domains is bounded by the size of a maximal bipartite minor. (author's abstract)Series: Preprint Series / Department of Applied Statistics and Data Processing
14
Rocha, Mário. "The embedding of complete bipartite graphs onto grids with a minimum grid cutwidth." CSUSB ScholarWorks, 2003. https://scholarworks.lib.csusb.edu/etd-project/2311.
Full text
15
Belkherchi, Nassim. "Contribution à l'étude du diagnostic et de la commande tolérante aux fautes par l'approche structurelle : application aux procédés biologiques." Phd thesis, Université Paul Sabatier - Toulouse III, 2011. http://tel.archives-ouvertes.fr/tel-00595600.
Full textAbstract:
Le travail réalisé dans cette thèse concerne l'étude du diagnostic de fautes et la reconfiguration en utilisant une approche issue de l'analyse structurelle et leurs applications sur un modèle de traitement des eaux usées. Dans une première partie, on fait un bref tour d'horizon sur la recherche dédiée au diagnostic et à la commande tolérante aux fautes, puis nous présentons les outils nécessaires de l'analyse structurelle. Ces derniers ont été appliqués sur l'approche choisie (l'approche structurelle) pour la détection et l'isolation de défauts, ainsi que pour la reconfiguration. Pour le diagnostic structurel, l'étape principale consiste à chercher les ensembles MSO qui servent à la génération des résidus. Une étude comparative de quelques algorithmes de recherche de ces ensembles a été faite pour choisir la méthode la plus efficace, la méthode choisie est celle de Krysander et al. La recherche des ensembles MSO est faite dans le sous système sur-déterminé. Pour l'amélioration de l'isolabilité structurelle, deux méthodes sont citées : la première consiste à considérer certaines fautes comme variables internes du système et la deuxième concerne l'ajout de capteurs. Pour la reconfiguration structurelle, on s'est basé sur les propriétés d'observabilité et de commandabilité structurelles. Notre but est de trouver la structure du système qui nous permet de garder les propriétés structurelles inchangées. Lors de l'application, nous étudions le cas où les fautes sont commises sur les actionneurs à savoir le débit de boues recyclées (Qr) et le débit de boues en excès (Qw), et sur les paramètres du système qui sont le taux maximum de croissance de la biomasse (µH,max) et la constante de Michaelis Menten (Ks).
16
Mighton, John 1957. "Knot theory on bipartite graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp03/NQ49930.pdf.
Full text
17
Ait-Aoudia, Samy. "Modélisation géométrique par contraintes : quelques méthodes de résolution." Phd thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 1994. http://tel.archives-ouvertes.fr/tel-00818347.
Full textAbstract:
Diverses techniques de modélisation sont utilisées en synthèse d'images et en CAO (conception assistée par ordinateur) pour produire des images réalistes et analyser les propriétés géométriques des objets solides modélisés. Cependant, malgré les progrès récents, la conception de formes géométriques reste une tâche complexe. Les objets géométriques que veut modéliser l'utilisateur doivent vérifier certaines propriétés, traditionnellement appelées contraintes. Pour pallier ces inconvénients certains systèmes de modélisation fournissent des outils de spécification des formes par des contraintes géométriques. Nous proposons dans cette thèse deux méthodes de résolution du système de contraintes. La première méthode étudie les graphes bipartis sous-jacents aux systèmes d'équations. Nous montrons qu'il est possible de décomposer polynomialement ces systèmes en sous-systèmes sur-contraints (plus d'équations que d'inconnues), sous-contraints (plus d'inconnues que d'équations) et bien-contraints (autant d'équations que d'inconnues) a partir du graphe biparti. La deuxième méthode proposée étudie les différentes configurations induites par des contraintes de distances, d'angles et de tangences entre points, droites et cercles. Les entités géométriques sont déterminées par un algorithme de réduction de graphes et un système à base de règles.
18
Aïder, Méziane. "Réseaux d'interconnexion bipartis colorations généralisées dans les graphes /." Grenoble 2 : ANRT, 1987. http://catalogue.bnf.fr/ark:/12148/cb37602131d.
Full text
19
Aïder, Méziane Payan Charles. "Réseaux d'interconnexion bipartis colorations généralisées dans les graphes /." S.l. : Université Grenoble 1, 2008. http://tel.archives-ouvertes.fr/tel-00325779.
Full text
20
Helmberg, Christoph, Israel Rocha, and Uwe Schwerdtfeger. "A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs." Universitätsbibliothek Chemnitz, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-175057.
Full textAbstract:
We give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph. This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.
21
Poole, Timothy Robert. "Factors in bipartite and other graphs." Thesis, University of Nottingham, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.403900.
Full text
22
Chakroun, Nasr Ali. "Problèmes de circuits, chemins et diamètres dans les graphes : routage dans les réseaux." Paris 11, 1986. http://www.theses.fr/1986PA112354.
Full textAbstract:
Cette thèse traite de différents problèmes liés à la théorie des graphes. La plupart des résultats sont liés à l’existence de circuits et de chemins, le reste est consacré à l’étude du diamètre et du routage. Le premier chapitre est consacré à l’étude du pancyclisme dans les graphes vérifiant une condition du type de celle de V. Chvatal et P. Erdos : la connectivité du graphe est supérieure ou égale à sa stabilité. Dans le deuxième chapitre nous nous intéressons aux graphes antisymétriques dont les degrés sont minorés. On y traite principalement des liens existants entre degrés et diamètre dans les graphes antisymétriques. Le troisième chapitre est axé sur la recherche de chemins et circuits dans les graphes bipartis orientés dont le nombre d’arcs ou les degrés sont minorés. Dans le quatrième chapitre, nous précisions la structure des graphes fortement connexes sans C≥₄. Le cinquième chapitre est la synthèse d’une étude sur le routage dans les réseaux d’interconnexion effectuée chez Thomson-C. S. F dans le cadre d’un projet de Réseau Numérique à Intégration de Service (RNIS), permettant de commuter des signaux à débits variables.
23
Koptelov, Maksim. "Link prediction in bipartite multi-layer networks, with an application to drug-target interaction prediction." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMC211.
Full textAbstract:
De nombreux problèmes réels relèvent d’une structure bi-relationnelle et peuvent être modélisés suivant des réseaux bipartis. Une telle modélisation permet l'utilisation de solutions standards pour la prédiction et/ou la recommandation de nouvelles relations entre objets de ces réseaux. La tâche de prédiction de liens est un problème largement étudié dans les réseaux simples, c’est-à-dire les réseaux avec un seul type d'interaction entre sommets. Cependant, pour les réseaux multicouche (i.e. réseaux avec plusieurs types d'arêtes entre sommets), ce problème n'est pas encore entièrement résolu.Cette thèse est motivée par l'importance d'une tâche réelle, à savoir la prédiction d'interaction entre un médicament et une cible thérapeutique. La recherche de candidats médicaments prometteurs pour une cible thérapeutique biologique donnée est une partie essentielle de la conception d’un médicament moderne. Dans cette thèse, nous modélisons ce problème comme une tâche de prédiction de lien dans un réseau multicouche biparti. Cette modélisation du problème permet de rassembler différentes sources d'information en une seule structure et ainsi d'améliorer la qualité de la prédiction d’un lien.Cette thèse se concentre sur le problème de la prédiction de liens dans les réseaux multicouches bipartis et apporte deux contributions principales à ce sujet. La première contribution est une solution pour résoudre la prédiction de liens sans limiter le nombre et le type de réseaux, ce qui est le principal défaut des méthodes de l'état de l'art. L'algorithme que nous avons développé modélise une marche aléatoire à la manière du PageRank et est capable de prédire de nouvelles interactions dans le réseau que nous construisons à partir de différentes sources d'information. La deuxième contribution, qui porte aussi sur ce problème, s’appuie sur les méthodes de détection de communautés. Cette solution, moins immédiate et plus dépendante du choix des valeurs des paramètres, donne de meilleurs résultats. Pour cela, nous adaptons des mesures utilisées pour la détection de communautés à la problématique de la prédiction de liens dans les réseaux multicouche bipartis et nous développons de nouvelles méthodes associant des communautés pour la prédiction de liens. Nous évaluons aussi nos méthodes sur des données autres que celles des interactions entre médicaments et cibles thérapeutiques montrant ainsi le caractère générique de notre approche.D’autre part, nous proposons un protocole expérimental de validation des interactions prédites reposant sur l’exploitation de ressources externes. Fondé sur une collection de concepts biomédicaux utilisés comme source de connaissances, ce protocole effectue une validation des paires de médicaments-cibles thérapeutiques qui sont prédites à partir de scores de confiance que nous avons définis. Une évaluation des interactions prédites sur des données tests montre l'efficacité de ce protocole.Enfin, nous nous intéressons au problème de l'identification et de la caractérisation de composés promiscues qui existe dans le processus de développement de médicaments. Nous modélisons ce problème comme une tâche de classification et le résolvons par l'apprentissage automatique. Notre contribution repose sur une approche d'exploration de graphes et d'échantillonnage. De plus, nous avons développé une interface graphique pour fournir un retour d'information aux experts sur les résultatsMany aspects from real life with bi-relational structure can be modeled as bipartite networks. This modeling allows the use of some standard solutions for prediction and/or recommendation of new relations between these objects in such networks. Known as the link prediction task, it is a widely studied problem in network science for single graphs, networks assuming one type of interaction between vertices. For multi-layer networks, allowing more than one type of edges between vertices, the problem is not yet fully solved.The motivation of this thesis comes from the importance of an application task, drug-target interaction prediction. Searching valid drug candidates for a given biological target is an essential part of modern drug development. In this thesis, the problem is modeled as link prediction in a bipartite multi-layer network. Modeling the problem in this setting helps to aggregate different sources of information into one single structure and as a result to improve the quality of link prediction.The thesis mostly focuses on the problem of link prediction in bipartite multi-layer networks and makes two main contributions on this topic.The first contribution provides a solution for solving link prediction in the given setting without limiting the number and type of networks, the main constrains of the state of the art methods. Modeling random walk in the fashion of PageRank, the algorithm that we developed is able to predict new interactions in the network constructed from different sources of information. The second contribution, which solves link prediction using community information, is less straight-forward and more dependent on fixing the parameters, but provides better results. Adopting existing community measures for link prediction to the case of bipartite multi-layer networks and proposing alternative ways for exploiting communities, the method offers better performance and efficiency. Additional evaluation on the data of a different origin than drug-target interactions demonstrate the genericness of proposed approach.In addition to the developed approaches, we propose a framework for validation of predicted interactions founded on an external resource. Based on a collection of biomedical concepts used as a knowledge source, the framework is able to perform validation of drug-target pairs using proposed confidence scores. An evaluation of predicted interactions performed on unseen data shows effectiveness of this framework.At the end, a problem of identification and characterization of promiscuous compounds existing in the drug development process is discussed. The problem is solved as a machine learning classification task. The contribution includes graph mining and sampling approaches. In addition, a graphical interface was developed to provide feedback of the result for experts
24
Omeroglu, Nurettin Burak. "K-way Partitioning Of Signed Bipartite Graphs." Master's thesis, METU, 2012. http://etd.lib.metu.edu.tr/upload/12614817/index.pdf.
Full textAbstract:
Clustering is the process in which data is differentiated, classified according to some criteria. As a result of partitioning process, data is grouped into clusters for specific purpose. In a social network, clustering of people is one of the most popular problems. Therefore, we mainly concentrated on finding an efficient algorithm for this problem. In our study, data is made up of two types of entities (e.g., people, groups vs. political issues, religious beliefs) and distinct from most previous works, signed weighted bipartite graphs are used to model relations among them. For the partitioning criterion, we use the strength of the opinions between the entities. Our main intention is to partition the data into k-clusters so that entities within clusters represent strong relationship. One such example from a political domain is the opinion of people on issues. Using the signed weights on the edges, these bipartite graphs can be partitioned into two or more clusters. In political domain, a cluster represents strong relationship among a group of people and a group of issues. After partitioning, each cluster in the result set contains like-minded people and advocated issues.
Our work introduces a general mechanism for k-way partitioning of signed bipartite graphs. One of the great advantages of our thesis is that it does not require any preliminary information about the structure of the input dataset. The idea has been illustrated on real and randomly generated data and promising results have been shown.
25
Newton, Matthew. "Sequential and parallel algorithms for low-crossing graph drawing." Thesis, Loughborough University, 2007. https://dspace.lboro.ac.uk/2134/12944.
Full textAbstract:
The one- and two-sided bipartite graph drawing problem alms to find a layout of a bipartite graph, with vertices of the two parts placed on parallel imaginary lines, that has the minimum number of edge-crossings. Vertices of one part are in fixed positions for the one-sided problem, whereas all vertices are free to move along their lines in the two-sided version. Many different heuristics exist for finding approximations to these problems, which are NP-hard. New sequential and parallel methods for producing drawings with low edgecrossings are investigated and compared to existing algorithms, notably Penalty Minimisation and Sifting, the current leaders. For the one-sided problem, new methods that include those based on simple stochastic hillclimbing, simulated annealing and genet.ic algorithms were tested. The new block-crossover genetic algorithm produced very good results with lower crossings than existing methods, although it tended to be slower. However, time was a secondary aim, the priority being to achieve low numbers of crossings. This algorithm can also be seeded with the output of an existing algorithm to improve results; combining with Penalty Minimisation in this way improved both the speed and number of crossings. Four parallel methods for the one-sided problem have been created, although two were abandoned because they gave bad results for even simple graphs. The other two methods, based on stochastic hill-climbing, produced acceptable results in faster times than similar sequential methods. PVM was used as the parallel communication system. Two new heuristics were studied for the two-sided problem, for which the only known existing method is to apply one-sided algorithms iteratively. The first is based on a heuristic for the linear arrangment problem; the second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The linear arrangement method based on the Koren-Harel multi-scale algorithm achieved the best results, outperforming iterative Barycentre (previously the best method) and iterative Penalty Minimisation. Another area of this work created three new heuristics for the k-planar drawing problem where k > 1. These are the first known practical algorithms to solve this problem. A sequential genetic algorithm based on TimGA is devised to work on k-planar graphs. Two parallel algorithms, one island model and the other a 'mesh' model, are also given. Comparison of results for k = 2 indicate that the parallel island method is better than the other two methods. MPI was used for the parallel communication. Overall, 14 new methods are introduced, of which 10 were developed into working algorithms. For the one-sided bipartite graph drawing problem the new block-crossover genetic algorithm can produce drawings with lower crossings than the current best available algorithms. The parallel methods do not perform as well as the sequential ones, although they generally achieved the same results faster. All of the new two-sided methods worked well; the weighted two-sided swap stochastic hill-climbing method was comparable to the existing best method, iterative Barycentre, and generally produced drawings with lower crossings, although it suffered with needing a good termination condition. The new methods based on the linear arrangement problem consistently produced drawings with lower crossings than iterative Barycentre, although they were nearly always slower. A new parallel algorithm for the k-planar drawing problem, based on the island model, generally created drawings with the lowest edge-crossings, although no algorithms were known to exist to make comparisons.
26
Alves, Deborah B. "Experiments on Universal Rigidity of Bipartite Graphs." Thesis, Harvard University, 2015. http://nrs.harvard.edu/urn-3:HUL.InstRepos:14398546.
Full textAbstract:
Our goal is to characterize necessary and sufficient conditions for the universal rigidity of bipartite frameworks. Previous work describe ways to test universal rigidity through semidefinite program- ming using stress matrix as a tool. Also, it had been shown a relationship between rigidity of a bipartite framework and quadric separability of the two sets of vertices. In particular, previous work showed that given a complete bipartite framework, separability by a quadric implied non- rigidity of the framework. Based on this, a reasonable conjecture was that the reciprocal could also be true. Our goal was to develop experiments using semidefinite programming to validate this conjecture for complete bipartite framework, and observe the behavior of rigidity for incomplete bipartite frameworks.
27
Benchettara, Nasserine. "Prévision de nouveaux liens dans les réseaux d'interactions bipartis : Application au calcul de recommandation." Paris 13, 2011. http://scbd-sto.univ-paris13.fr/secure/edgalilee_th_2011_benchettara.pdf.
Full textAbstract:
Dans cette thèse, nous étudions le problème de la prévision d'apparition de nouveaux liens dans les réseaux d'interactions. Nous nous intéressons en particulier aux réseaux dynamiques ayant une structure bipartite. Nous proposons un modèle de prévision de liens utilisant les techniques d'apprentissage automatique supervisé. Le problème de prévision de liens est considéré dans ce cas comme un problème de classification binaire. Notre approche applique un schéma de propositionnalisation où chaque paire de noeuds est décrite par un ensemble d'attributs représentant des mesures topologiques. Ces mesures sont calculées dans le graphe biparti et dans les graphes projetés qui en découlent. Nous montrons que ces nouvelles similarités dites " indirectes " apportent un gain d'information bénéfique par rapport aux seules similarités directes. Cette thèse apporte aussi de nouvelles solutions au problème de déséquilibre des données dû à la disproportion inhérente entre le nombre de liens qui peuvent se former et le nombre de liens qui se forment réellement. Nous proposons tout d'abord d'utiliser des méthodes de sous-échantillonnage informé pour réduire le déséquilibre. Une deuxième solution au niveau algorithmique consiste en une approche d'apprentissage semi-supervisé. Dans ce cas, le problème de prévision de liens est vu comme un problème d'apprentissage à partir d'un ensemble d'instances étiquetées (classe minoritaire) et un ensemble d'instances non-étiquetées (classe majoritaire). Nous montrons que cette nouvelle approche permet d'améliorer les performances du classifieur sur la classe minoritaire. Les différentes approches proposées sont appliquées sur les données réelles dans le cadre de deux applications : recommandation de collaborations académiques et recommandation de produits dans un site de vente de musique en ligneIn this work, we handle the problem of new link prediction in dynamic complex networks. We mainly focus on studying networks having a bipartite underlaying structure. We propose to apply a propositionnalization approach where each couple of nodes in the network is described by a set of topological measures. One first contribution in this thesis is to consider measures computed in the bipartite graph and also in the associated projected graphs. A supervised machine learning approach is applied. This approach though it gives some good results, suffers from the obvious problem of class skewness. We hence focus on handling this problem. Informed sub-sampling approaches are first proposed. A semi-supervised machine learning approach is also applied. All proposed approaches are applied and evaluated on real datasets used in real application of academic collaboration recommendation and product recommendation in an e-commerce site
28
Uduman, Mohamed. "Identifying the largest complete data set from ALFRED /." Link to online version, 2006. https://ritdml.rit.edu/dspace/handle/1850/1876.
Full text
29
Renman, Jonatan. "One-sided interval edge-colorings of bipartite graphs." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-171753.
Full textAbstract:
A graph is an ordered pair composed by a set of vertices and a set of edges, the latter consisting of unordered pairs of vertices. Two vertices in such a pair are each others neighbors. Two edges are adjacent if they share a common vertex. Denote the amount of edges that share a specific vertex as the degree of the vertex. A proper edge-coloring of a graph is an assignment of colors from some finite set, to the edges of a graph where no two adjacent edges have the same color. A bipartition (X,Y) of a set of vertices V is an ordered pair of two disjoint sets of vertices such that V is the union of X and Y, where all the vertices in X only have neighbors in Y and vice versa. A bipartite graph is a graph whose vertices admit a bipartition (X,Y). Let G be one such graph. An X-interval coloring of G is a proper edge coloring where the colors of the edges incident to each vertex in X form an interval of integers. Denote by χ'int(G,X) the least number of colors needed for an X-interval coloring of G. In this paper we prove that if G is a bipartite graph with maximum degree 3n (n is a natural number), where all the vertices in X have degree 3, then
30
Kadi, Abderrezzak Mohamed El. "Existence de cycles dans les graphes bipartis et dans plusieurs familles de graphes généralisant la classe des graphes sans K₁,₃." Paris 11, 1999. http://www.theses.fr/1999PA112401.
Full textAbstract:
Dans cette thèse, nous apportons une contribution à l'étude de l'existence de cycles de longueur donnée dans certaines familles de graphes. La thèse se divise en deux parties. La première partie est dédiée aux graphes bipartis. Nous nous y intéressons aux graphes bipartis équilibrés hamiltoniens, bipancycliques, S-cyclables et S-pancyclables. Les conditions envisagées portent sur les degrés, le nombre d'indépendance biparti et la k-bifermeture. La seconde partie concerne les graphes sans K₁,₃ que nous appellerons aussi graphes "claw-free". On examine dans cette partie plusieurs familles de graphes qui généralisent la classe des graphes sans K₁,₃ , en particulier la famille des graphes λ-claw-free et celle des graphes sans S(K₁,₃), et l'on s'intéresse aux propriétés d'existence de cycles dans ces familles de graphes ou dans leurs carrésIn this thesis, we study sufficient conditions for the existence of cycles of given length in several families of graphs. The thesis consists of two parts: The first one is dedicated to bipartite graphs. We consider mainly bipartite balanced graphs that are hamiltonian, bipancyclic, S-cyclable and S-pancyclable. The conditions we investigate concern degree, independence number and k-biclosure. The second part concerns claw-free graphs. We examine several families that generalize the claw-free graphs family, mainly the λ-claw-free graphs and the S(K₁,₃)-free graphs. We look for sufficient conditions that insure some special cycles in those families of graphs or in their squares
31
Hamzaoui, Amel. "Shared-Neighbours methods for visual content structuring and mining." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00856582.
Full textAbstract:
This thesis investigates new clustering paradigms and algorithms based on the principle of the shared nearest-neighbors (SNN. As most other graph-based clustering approaches, SNN methods are actually well suited to overcome data complexity, heterogeneity and high-dimensionality.The first contribution of the thesis is to revisit existing shared neighbors methods in two points. We first introduce a new SNN formalism based on the theory of a contrario decision. This allows us to derive more reliable connectivity scores of candidate clusters and a more intuitive interpretation of locally optimum neighborhoods. We also propose a new factorization algorithm for speeding-up the intensive computation of the required sharedneighbors matrices.The second contribution of the thesis is a generalization of the SNN clustering approach to the multi-source case. Whereas SNN methods appear to be ideally suited to sets of heterogeneous information sources, this multi-source problem was surprisingly not addressed in the literature beforehand. The main originality of our approach is that we introduce an information source selection step in the computation of candidate cluster scores. As shown in the experiments, this source selection step makes our approach widely robust to the presence of locally outlier sources. This new method is applied to a wide range of problems including multimodal structuring of image collections and subspace-based clustering based on random projections. The third contribution of the thesis is an attempt to extend SNN methods to the context of bipartite k-nn graphs. We introduce new SNN relevance measures revisited for this asymmetric context and show that they can be used to select locally optimal bi-partite clusters. Accordingly, we propose a new bipartite SNN clustering algorithm that is applied to visual object's discovery based on a randomly precomputed matching graph. Experiments show that this new method outperformed state-of-the-art object mining results on OxfordBuilding dataset. Based on the discovered objects, we also introduce a new visual search paradigm, i.e. object-based visual query suggestion.
32
Chen, Yan. "Enhanced Web Search Engines with Query-Concept Bipartite Graphs." Digital Archive @ GSU, 2010. http://digitalarchive.gsu.edu/cs_diss/54.
Full textAbstract:
With rapid growth of information on the Web, Web search engines have gained great momentum for exploiting valuable Web resources. Although keywords-based Web search engines provide relevant search results in response to users’ queries, future enhancement is still needed. Three important issues include (1) search results can be diverse because ambiguous keywords in queries can be interpreted to different meanings; (2) indentifying keywords in long queries is difficult for search engines; and (3) generating query-specific Web page summaries is desirable for Web search results’ previews. Based on clickthrough data, this thesis proposes a query-concept bipartite graph for representing queries’ relations, and applies the queries’ relations to applications such as (1) personalized query suggestions, (2) long queries Web searches and (3) query-specific Web page summarization. Experimental results show that query-concept bipartite graphs are useful for performance improvement for the three applications.
33
Watts, Valerie Lynn. "Covers and partitions of graphs by complete bipartite subgraphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/NQ63469.pdf.
Full text
34
Xia, Hui. "Visual medical decision-making: Bipartite graphs vs. interactive tables." Thesis, University of Ottawa (Canada), 1996. http://hdl.handle.net/10393/9562.
Full textAbstract:
Most of the current medical diagnosis support systems are based on a textual design. In this thesis we present a model that uses a different design. It uses visualization to aid home diagnosis of common diseases in a user-friendly way. The model clearly displays the diagnostic results on the screen. A way of organizing the information into a picture of all symptoms, diseases, and the complex relationships between them (especially the combination of symptoms onto a single screen to give a global view) is presented. The purpose of designing this model is to bring complicated medical knowledge to the ordinary user. We believe that the simplified and economic display can demystify medicine, and empower the user to take better care of himself. By this convenient software tool people can discover quickly at home whether their symptom is serious or not, and then decide whether it is necessary to see the doctor; also people can compare the diagnosis the model makes with the doctors'. This model does not recommend treatment or therapy.
35
Dimitrov, Youri. "Polynomially-divided solutions of bipartite self-differential functional equations." Columbus, Ohio : Ohio State University, 2006. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1155149204.
Full text
36
Crenshaw, Cameron M. "Edge-Transitive Bipartite Direct Products." VCU Scholars Compass, 2017. http://scholarscompass.vcu.edu/etd/4801.
Full textAbstract:
In their recent paper ``Edge-transitive products," Hammack, Imrich, and Klavzar showed that the direct product of connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive, and at least one is arc-transitive. However, little is known when the product is bipartite. This thesis extends this result (in part) for the case of bipartite graphs using a new technique called "stacking." For R-thin, connected, bipartite graphs A and B, we show that A x B is arc-transitive if and only if A and B are both arc-transitive. Further, we show A x B is edge-transitive only if at least one of A, B is also edge-transitive, and give evidence that strongly suggests that in fact both factors must be edge-transitive.
37
Hazim, Sharif Walied. "L'extension respectueuse entre posets à hauteur constante et ses rapports avec les graphes bipartis (ou tableaux bivalents)." Aix-Marseille 1, 1993. http://www.theses.fr/1993AIX11041.
Full textAbstract:
Mon travail de these porte principalement sur l'etude de l'extension respectueuse entre posets a hauteur constante et ses rapports avec les graphes bipartis (ou tableaux bivalents). Le probleme d'extension respectueuse est trivial pour la classe de toutes les relations binaires ou pour la classe des posets finis. Cependant, il devient interessant avec la condition d'une hauteur constante h, ce que nous appelons h-extensibilite. Nous avons etudie des exemples de posets h-extensibles et de posets 2- inextensibles. Nous avons transforme les posets de hauteur 2 en tableaux bivalents et avons fait une comparaison entre l'extension respectueuse des posets finis de hauteur 2 et celle des tableaux bivalents. Nous donnons des exemples de tableaux bivalents inextensibles. En appendice, nous avons etudie le probleme d'unimodalite
38
Werner, Rose-Line. "Concrete constructions of unbalanced bipartite expander graphs and generalized conductors." Zürich : ETH, Eidgenössische Technische Hochschule Zürich, Departement Informatik, Institut für Informationssysteme, 2008. http://e-collection.ethbib.ethz.ch/show?type=dipl&nr=389.
Full text
39
Portakal, Irem [Verfasser]. "Rigidity of toric varieties associated to bipartite graphs / Irem Portakal." Berlin : Freie Universität Berlin, 2018. http://d-nb.info/1196803293/34.
Full text
40
Surber, Wesley M. "Restricted and Unrestricted Coverings of Complete Bipartite Graphs with Hexagons." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/etd/1136.
Full textAbstract:
A minimal covering of a graph G with isomorphic copies of graph H is a set {H1, H2, H3, ... , Hn} where Hi is isomorphic to H, the vertex set of Hi is a subset of G, the edge set of G is a subset of the union of Hi's, and the cardinality of the union of Hi's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of Hi is the subset of the edge set of G for all i which implies no additional restrictions. However, if G is not the complete graph, then this condition may have implications. We will give necessary and sufficient conditions for minimal coverings of complete bipartite graph with 6-cycles, which we call minimal unrestricted coverings. We also give necessary and sufficient conditions for minimal coverings of the complete bipartite graph with 6-cycles with the added condition the edge set of Hi is a subset of G for all i, and call these minimal restricted coverings.
41
Melinder, Victor. "Upper bounds on the star chromatic index for bipartite graphs." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-164938.
Full textAbstract:
An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted
42
Ye, Jiacheng. "Computing Exact Bottleneck Distance on Random Point Sets." Thesis, Virginia Tech, 2020. http://hdl.handle.net/10919/98669.
Full textAbstract:
Given a complete bipartite graph on two sets of points containing n points each, in a bottleneck matching problem, we want to find an one-to-one correspondence, also called a matching, that minimizes the length of its largest edge; the length of an edge is simply the Euclidean distance between its end-points. As an application, consider matching taxis to requests while minimizing the largest distance between any request to its matched taxi. The length of the largest edge (also called the bottleneck distance) has numerous applications in machine learning as well as topological data analysis. One can use the classical Hopcroft-Karp (HK-) Algorithm to find the bottleneck matching. In this thesis, we consider the case where A and B are points that are generated uniformly at random from a unit square. Instead of the classical HK-Algorithm, we implement and empirically analyze a new algorithm by Lahn and Raghvendra (Symposium on Computational Geometry, 2019). Our experiments show that our approach outperforms the HK-Algorithm based approach for computing bottleneck matching.Master of Science
Consider the problem of matching taxis to an equal number of requests. While matching them, one objective is to minimize the largest distance between a request and its match. Finding such a matching is called the bottleneck matching problem. In addition, this optimization problem arises in topological data analysis as well as machine learning. In this thesis, I conduct an empirical analysis of a new algorithm, which is called the FAST-MATCH algorithm, to find the bottleneck matching. I find that, when a large input data is randomly generated from a unit square, the FAST-MATCH algorithm performs substantially faster than the classical methods
43
Puffenberger, Owen. "Uniqueness of Bipartite Factors in Prime Factorizations Over the Direct Product of Graphs." VCU Scholars Compass, 2013. http://scholarscompass.vcu.edu/etd/3017.
Full textAbstract:
While it has been known for some time that connected non-bipartite graphs have unique prime factorizations over the direct product, the same cannot be said of bipartite graphs. This is somewhat vexing, as bipartite graphs do have unique prime factorizations over other graph products (the Cartesian product, for example). However, it is fairly easy to show that a connected bipartite graph has only one prime bipartite factor, which begs the question: is such a prime bipartite factor unique? In other words, although a connected bipartite graph may have multiple prime factorizations over the direct product, do such factorizations contain the same prime bipartite factor? It has previously been shown by Hammack that when the prime bipartite factor is K_2, this is in fact true. The goal of this paper is to prove that this is in fact true for any prime bipartite factor, provided the graph being factored is R-thin. The proof of the main result takes the same initial approach as the proof by Hammack, before moving into new territory in order to prove the final result.
44
Allali, Oussama. "Structure et dynamique des graphes de terrain bipartis : liens internes et prédiction de liens." Paris 6, 2011. http://www.theses.fr/2011PA066201.
Full textAbstract:
Beaucoup de graphes de terrain comme les relations acteur-film ou fichier-fournisseur sont modélisables par des graphes bipartis, dont les noeuds sont divisés en deux ensembles avec des liens entre les noeuds de différents ensembles seulement. Cependant, des méthodes manquent actuellement pour analyser correctement ces graphes, la plupart des méthodes existantes étant conçues pour des graphes classiques. Une approche courante, mais limitée, consiste à transformer les graphes bipartis en graphes classiques, par un procédé appelé projection. Cependant ceci entraîne une perte importante d'informations. Nous introduisons dans cette thèse les liens internes, et les proposons comme une nouvelle notion importante pour analyser les graphes de terrain bipartis : elle permet de mesurer la redondance dans ces graphes, et de mesurer la perte d'information entre un graphe biparti et ses projections. Nous montrons en étudiant différents jeux de données que les liens internes sont très fréquents, et que les statistiques associées permettent de souligner leurs ressemblances et leurs différences avec les graphes bipartis aléatoires. Ensuite, nous montrons que nous pouvons tirer profit de cette notion pour modéliser les graphes de terrain bipartis et les stocker dans un format compact. La plupart des graphes de terrain sont de plus dynamiques, c'est-à-dire que leur structure évolue au fil du temps par l'ajout et/ou le retrait de noeuds et/ou de liens. L'étude de la dynamique des graphes de terrain peut s'aborder par le problème de la prédiction de nouveaux liens dans ces graphes. Plusieurs travaux ont étudié le problème de la prédiction de liens dans les graphes classique (non-bipartis). Toutefois, leurs méthodes ne sont pas directement applicables aux graphes bipartis ou sont inappropriées. Nous proposons une approche basée sur les liens internes pour la prédiction dans les graphes bipartis. Nous montrons que notre méthode fonctionne très bien, beaucoup mieux que l'approche de recommandation classique.
45
Hanika, Tom [Verfasser]. "Discovering Knowledge in Bipartite Graphs with Formal Concept Analysis / Tom Hanika." Kassel : Universitätsbibliothek Kassel, 2019. http://d-nb.info/1180660811/34.
Full text
46
Koo, Cheng Wai. "A Bound on the Number of Spanning Trees in Bipartite Graphs." Scholarship @ Claremont, 2016. https://scholarship.claremont.edu/hmc_theses/73.
Full textAbstract:
Richard Ehrenborg conjectured that in a bipartite graph G with parts X and Y, the number of spanning trees is at most the product of the vertex degrees divided by |X|⋅|Y|. We make two main contributions. First, using techniques from spectral graph theory, we show that the conjecture holds for sufficiently dense graphs containing a cut vertex of degree 2. Second, using electrical network analysis, we show that the conjecture holds under the operation of removing an edge whose endpoints have sufficiently large degrees.
Our other results are combinatorial proofs that the conjecture holds for graphs having |X| ≤ 2, for even cycles, and under the operation of connecting two graphs by a new edge.
We also make two new conjectures based on empirical data, each of which is stronger than Ehrenborg's conjecture.
47
Mumba, Nephtale Bvalamanja. "Codes, graphs and designs from maximal subgroups of alternating groups." University of the Western Cape, 2018. http://hdl.handle.net/11394/6165.
Full textAbstract:
Philosophiae Doctor - PhD (Mathematics)The main theme of this thesis is the construction of linear codes from adjacency matrices or sub-matrices of adjacency matrices of regular graphs. We first examine the binary codes from the row span of biadjacency matrices and their transposes for some classes of bipartite graphs. In this case we consider a sub-matrix of an adjacency matrix of a graph as the generator of the code. We then shift our attention to uniform subset graphs by exploring the automorphism groups of graph covers and some classes of uniform subset graphs. In the sequel, we explore equal codes from adjacency matrices of non-isomorphic uniform subset graphs and finally consider codes generated by an adjacency matrix formed by adding adjacency matrices of two classes of uniform subset graphs.
48
Mahjoub, Ali Ridha. "Étude de structures combinatoires issues de la physique statistique et d'autres domaines." Habilitation à diriger des recherches, 1985. http://tel.archives-ouvertes.fr/tel-00315955.
Full textAbstract:
Étude de certains problèmes d'optimisation combinatoire. Le premier concerne un problème de régulation de trafic pour lequel on donne une formulation mathématique et on propose une méthode permettant de le résoudre. Le deuxième problème traité est un des problèmes de la physique statistique qui relève de la combinatoire et de l'optimisation, celui du fondamental d'un verre de spins (modèle d'Ising). Enfin on étudie, deux autres problèmes d'optimisation combinatoire: l'absorbant et le Ki-recouvrement de poids minimum
49
Curtin, Brian. "Bipartite distance-regular graphs." 1996. http://catalog.hathitrust.org/api/volumes/oclc/35869101.html.
Full textAbstract:
Thesis (Ph. D.)--University of Wisconsin--Madison, 1996.Typescript. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 145-146).
50
Yueh-Shin, Lee, and 李岳勳. "Counting Bipartite Steinhaus Graphs." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/44889009486153797119.
Full textAbstract:
碩士國立交通大學
應用數學研究所
82
A Steinhaus matrix is a symmetric $0-1$ matrix $[a_{i,j}]_{n \times n}$ such that $a_{i,i}=0$ for $0 \leq i \leq n-1$ and $a_{i,j}=(a_{i-1,j-1}+a_{i-1,j}) \pmod 2$ for $1 \leq i