To see the other types of publications on this topic, follow the link: Bipartit.
Dissertations / Theses on the topic 'Bipartit'
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 'Bipartit.'
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
Lissel, Erik. "Korsningar i kompletta multipartita grafer." Thesis, Örebro universitet, Institutionen för naturvetenskap och teknik, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:oru:diva-35367.
Full textAbstract:
Syftet med den här uppsatsen är att undersöka graden av planäritet för kompletta multipartita grafer. Det primära resultatet som presenteras är en formel som kan användas för att nedåt begränsa det minsta antalet korsningar som behövs för att realisera en komplett bipartit graf indelad i m respektive n noder: cr(K_{m,,n}) >= q - 2p + 4, m >= n >= 2, där q = mn och p = m + n. Därutöver presenteras tabeller som med formeln som utgångspunkt uppskattar eller bestämmer det minsta antalet korsningar för alla kompletta multipartita grafer med sju noder eller mindre. Uppsatsen innehåller också en genomgång av några tidigare resultat, däribland Zarankiewicz uppställning av kompletta bipartita grafer samt en överblick över Crossing Number Inequality
2
Zhang, Ganqin. "Bipartite RankBoost+: An Improvement to Bipartite RankBoost." Case Western Reserve University School of Graduate Studies / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=case160767885657324.
Full text
3
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
4
Kaihara, Marcelo E., 直史 高木, and Naofumi Takagi. "Bipartite Modular Multiplication." Springer, 2005. http://hdl.handle.net/2237/2751.
Full text
5
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.
6
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.
7
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
8
Saugmann, Pil Maria. "Frustration in a bipartite lattice." Licentiate thesis, Stockholms universitet, Fysikum, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-161721.
Full text
9
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.
10
Lima, Murilo Santos de. "Aproximação de métricas finitas por métricas arbóreas e aplicações." Universidade de São Paulo, 2011. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13032012-201516/.
Full textAbstract:
Muitos problemas de otimização em grafos, em especial problemas métricos, são mais fáceis de resolver em árvores. Portanto, uma estratégia para obter um bom algoritmo para certos problemas é obter uma árvore que aproxime o grafo, e utilizar uma solução do problema nessa árvore como uma solução aproximada para o problema no grafo original. Neste trabalho é estudada a técnica de Fakcharoenphol, Rao e Talwar, que mostraram como aproximar uma métrica finita arbitrária com n pontos por uma métrica numa árvore com distorção esperada O(lg n) -- o ótimo assintótico. Essa estratégia resulta em algoritmos de aproximação com boas razões de aproximação, e em algoritmos com bom fator de competitividade para diversos problemas de otimização online e distribuídos. É apresentada especificamente a aplicação da técnica ao problema do emparelhamento mínimo bipartido online, que ilustra como a aproximação de métricas auxilia na resolução de um problema e os cuidados que devem ser tomados nessa aplicação.Many optimization problems on graphs, especially metric problems, are easier to solve on trees. Therefore, a strategy for obtaining a good algorithm for certain problems is to obtain a tree that approximates the graph, and use a solution of the problem on the tree as an approximate solution for the problem on the original graph. We study the work of Fakcharoenphol, Rao e Talwar, who showed how to approximate an arbitrary finite metric on n points by a tree metric with expected distortion O(lg n), which is asymptotically optimum. This strategy leads to algorithms with good approximation factors, and to competitive algorithms for various optimization problems, some of them online and distributed. Here, we present the application of that technique to the problem of finding a minimum online matching on a bipartite metric graph. This problem illustrates how metric approximation aids in solving a problem, and the care that must be taken when doing such an application.
11
Ioannou, L. M. "Computing finite-dimensional bipartite quantum separability." Thesis, University of Cambridge, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.604939.
Full textAbstract:
In Chapter 2, I apply polyhedral theory to prove easily that the set of separable states is not a polytope; for the sake of completeness, I then review the role of polytopes in nonlocality. Next, I give a novel treatment of entanglement witnesses and define a new class of entanglement witnesses, which may prove to be useful beyond the examples given. In the last section, I briefly review the five basic convex body problems given in [1] (Groetschel et al., 1988), and their application to the quantum separability problem. In Chapter 3, I treat the separability problem as a computational decision problem and motivate its approximate formulations. After a review of basic complexity-theoretic notions, I discuss the computational complexity of the separability problems: I discuss the issue of NP-completeness, giving an alternative definition of the separability problem as an NP-hard problem in NP. I finish the chapter with a comprehensive survey of deterministic algorithm solutions to the separability problem, including one that follows from a second NP formulation. Chapters 1 and 3 motivate a new interior-point algorithm which, given the expected values of a subset of an orthogonal basis of observables of an otherwise unknown quantum state, searches for an entanglement witnesses in the span of the subset of observables. When all the expected values are known, the algorithm solves the separability problem. In Chapter 4, I give the motivation for the algorithm and show how it can be used in a particular physical scenario to detect entanglement (or decade separability) of an unknown quantum state using as few quantum resources as possible. I then explain the intuitive idea behind the algorithm and relate it to the standard algorithms of its kind. I end the chapter with a comparison of the complexities of the algorithms surveyed in Chapter 3. Finally, in Chapter 5, I present the details of the algorithm and discuss its performance relative to standard methods.
12
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
13
Bowlin, Garry. "Maximum frustration of bipartite signed graphs." Diss., Online access via UMI:, 2009.
Find full text
14
Shafie, Sharil Idzwan. "Active modules of bipartite metabolic network." Thesis, University of Birmingham, 2018. http://etheses.bham.ac.uk//id/eprint/8635/.
Full textAbstract:
The thesis investigates the problem of identifying active modules of bipartite metabolic network. We devise a method of motif projection, and the extraction of clusters from active modules based on the concentration of active-motifs in the network. Our results reveal the existence of hierarchical structure. We model regulation of metabolism as an interaction between a metabolic network and a gene regulatory network in the form of interconnected network. We devise two module detection algorithms for interconnected network to evaluate the molecular changes of activity that are associated with cellular responses. The first module detection algorithm is formulated based on information map of random walks that is capable of inferring modules based on topological and activity of nodes. The proposed algorithm has faster execution time and produces comparably close performance as previous work. The second algorithm takes into account of strong regulatory activities in the gene regulatory layer to support the active regions in the metabolic layer. The integration of gene information allows the formation of large modules with better recall. In conclusion, our findings indicate the importance of no longer modelling complex biological systems as a single network, but to view them as flow of information of multiple molecular spaces.
15
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
16
Nguyen, Hai Nam. "Pattern Detection in Bipartite Temporal Network." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-393215.
Full textAbstract:
Pattern detection in social networks has been of great interest recently because it helps to reveal insights about how people communicate. In graph mining, this is referred to as a frequent sub-graphs mining problem and it has many variations regarding the structure of the network - i.e. how much information the graph holds. As a part of the evolution of the problem, additional information such as data dimensions or more advanced network structure are incorporated to the input to find more interesting hidden patterns. This thesis concerns finding patterns in Twitter data modeled as a bipartite network with an additional temporal dimension. After defining three topology-based types of pattern mathematically, three pattern detection methods are developed, implemented and tested on real-world data collected from Twitter. The results reveal the most popular patterns of each type on Twitter data, a decaying tendency in the replying time as the conversation develops and other interesting observations. They also show that using the difference between two consecutive messages in a pattern (time leap) could be a good alternative time constraint for a time window in pattern detection. Despite being run on a small number of test cases, the results successfully demonstrate the potential of studying chain-like patterns separated from the dominant star-like ones in social networks like Twitter.
17
Beckett, Stephen J. "Nestedness and modularity in bipartite networks." Thesis, University of Exeter, 2015. http://hdl.handle.net/10871/17913.
Full textAbstract:
Bipartite networks are a useful way of representing interactions between two sets of entities. Understanding the underlying structures of such networks may give insights into the functionality and behaviour of the systems they represent. Two important structural patterns identified in bipartite networks are nestedness and modularity. Nestedness describes a hierarchical ordering of nodes such that more specialised nodes have interactions with a subset of the partners with which the more generalised nodes interact. Modularity captures the community structure of a network as distinct clusters of interactions, such that there are more connections within communities than between communities. While these network architectures are easy to describe in writing, their quantitative measurement for a given network is a difficult task. Several different methods have been proposed in each case and it is currently unclear which of them should be used in practice. This thesis considers the use, measurement and interpretation of nestedness and modularity in bipartite networks. First, it is shown how bipartite networks can be an effective tool for linking data and theory in community ecology, though use of a coevolutionary model of virus-bacteria interactions. Next, a series of studies is presented that push towards clarification of the best procedures to measure nestedness and modularity in bipartite networks. Robustness of nestedness measures is tested on a synthetic ensemble of networks, showing that apparent nestedness depends strongly on the choice of measure, null model and effect size statistics. Recommendations for performing nestedness are made with relation to individual and cross-network comparisons. Additionally, a new algorithm for identifying weighted modularity is proposed that can be shown to outperform existing methods. Crucially, it is shown that quantitative modular structures differ from traditional binary modular structures with implications for how modularity is reported and used. Improving the way in which nestedness and modularity are measured is a necessary step for integrating data and theory in bipartite networks.
18
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.
19
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
20
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.
21
Šafárová, Marcela. "Bipartitní grafy pro analýzu mikrobiomů." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2017. http://www.nusl.cz/ntk/nusl-316849.
Full textAbstract:
Microorganisms are all around us. Some of them even live in our body and are essential for our healthy being. Study of microbial communities based on their genetic content has become very popular with the development of new technologies, which enable easy reading of DNA or RNA. The key role of these studies is usually to characterize significant microbial patterns of an environment. However, currently used visualization tools have many drawbacks for such analyses. The subject of this thesis is to design a R/Bioconductor package for simple creation of bipartite graphs from microbial data. This type of visualization brings many advantages for microbiome analysis. Benefits of bipartite graphs are further demonstrated by analysis of main parameters affecting computer processing of microbial data.
22
Borivoj, Subotić. "Grafovske metode u geometriji i geometrijske metode u grafovima." Phd thesis, Univerzitet u Novom Sadu, Prirodno-matematički fakultet u Novom Sadu, 2005. https://www.cris.uns.ac.rs/record.jsf?recordId=73402&source=NDLTD&language=en.
Full textAbstract:
U prvoj glavi dat je prikaz osnovnih pojmova koji se koriste u tezi, sa naglaskom na osnovne pojmove teorije grafova. U drugoj glavi daju se grafovski dokazi nekih geometrijskih problema. Na primer, dajemo dokaz poznate teoreme Silvestra. iz Kombinatorne geometrije, koristeći grafove. Treće poglavlje sadrži neke geometrijske dokaze u grafovima. Na primer, poznatu Turanovu teoremu, Pikovu teoremu i drugo. U četvrtom poglavlju dajemo metodičku transformaciju prethodnih problema. Neki od problema razloženi su na delove koji se mogu prezentirati od osnovne škole do poslediplomskih studija. Peto poglavlje sadrži komentare prethodnog, kao i preporuku UNESCO-a iz 1992. godine o obrazovanju učenika u novom milenijumu.Chapter 1 contains a shoot review of the basic notions which are used in the thesis with emphasis on the basic notions of graph theory. In Chapter 2we present graph proofs of some geometrical problems. For example, we present some proofs of the well known theorem of Sylvester, from Combinatorial geometry, using graph methods. In Chapter 3 we present some proofs in graphs which use geometry. For example, famous Turan’s theorem, Pick’s theorem and some others. Chapter 4 contains methodology transformations i.e. we apply the results from the previous chapters to the situations in the clossroom. In Chapter 5 we have some comments of UNESCO, from 1992, on education of children.
23
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
24
Sng, Colin Thiam Soon. "Efficient algorithms for bipartite matching problems with preferences." Thesis, University of Glasgow, 2008. http://theses.gla.ac.uk/301/.
Full textAbstract:
Matching problems involve a set of participants, where each participant has a capacity and a subset of the participants rank a subset of the others in order of preference (strictly or with ties). Matching problems are motivated in practice by large-scale applications, such as automated matching schemes, which assign participants together based on their preferences over one another. This thesis focuses on bipartite matching problems in which there are two disjoint sets of participants (such as medical students and hospitals). We present a range of efficient algorithms for finding various types of optimal matchings in the context of these problems. Our optimality criteria involve a diverse range of concepts that are alternatives to classical stability. Examples include so-called popular and Pareto optimal matchings, and also matchings that are optimal with respect to their profile (the number of participants obtaining their first choice, second choice and so on). The first optimality criterion that we study is the notion of a Pareto optimal matching, a criterion that economists regard as a fundamental property to be satisfied by an optimal matching. We present the first algorithmic results on Pareto optimality for the Capacitated House Allocation problem (CHA), which is a many-to-one variant of the classical House Allocation problem, as well as for the Hospitals-Residents problem (HR), a generalisation of the classical Stable Marriage problem. For each of these problems, we obtain a characterisation of Pareto optimal matchings, and then use this to obtain a polynomial-time algorithm for finding a maximum Pareto optimal matching. The next optimality criterion that we study is the notion of a popular matching. We study popular matchings in CHA and present a polynomial-time algorithm for finding a maximum popular matching or reporting that none exists, given any instance of CHA. We extend our findings to the case in CHA where preferences may contain ties (CHAT) by proving the extension of a well-known result in matching theory to the capacitated bipartite graph case, and using this to obtain a polynomial-time algorithm for finding a maximum popular matching, or reporting that none exists. We next study popular matchings in the Weighted Capacitated House Allocation problem (WCHA), which is a variant of CHA where the agents have weights assigned to them. We identify a structure in the underlying graph of the problem that singles out those edges that cannot belong to a popular matching. We then use this to construct a polynomial-time algorithm for finding a maximum popular matching or reporting that none exists, for the case where preferences are strict. We then study popular matchings in a variant of the classical Stable Marriage problem with Ties and Incomplete preference lists (SMTI), where preference lists are symmetric. Here, we provide the first characterisation results on popular matchings in the bipartite setting where preferences are two-sided, which can either lead to a polynomial-time algorithm for solving the problem or help establish that it is NP-complete. We also provide the first algorithm for testing if a matching is popular in such a setting. The remaining optimality criteria that we study involve profile-based optimal matchings. We define three versions of what it means for a matching to be optimal based on its profile, namely so-called greedy maximum, rank-maximal and generous maximum matchings. We study each of these in the context of CHAT and the Hospitals-Residents problem with Ties (HRT). For each problem model, we give polynomial-time algorithms for finding a greedy maximum, a rank-maximal and a generous maximum matching.
25
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
26
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
27
Sng, Colin. "Efficient algorithms for bipartite matching problems with preferences." Connect to e-thesis, 2008. http://theses.gla.ac.uk/301/.
Full textAbstract:
Thesis (Ph.D.) - University of Glasgow, 2008.Ph.D. thesis submitted to the Department of Computing Science, Faculty of Information and Mathematical Sciences, University of Glasgow, 2008. Includes bibliographical references. Print version also available.
28
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 [...]
29
Tang, Tang. "Monitoring Estrogen Receptor Dimerization via Bipartite Tetracysteine Display." Ohio University / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1562622108928366.
Full text
30
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
31
Deymier, P. A., and K. Runge. "Non-separable states in a bipartite elastic system." AMER INST PHYSICS, 2017. http://hdl.handle.net/10150/624037.
Full textAbstract:
We consider two one-dimensional harmonic chains coupled along their length via linear springs. Casting the elastic wave equation for this system in a Dirac-like form reveals a directional representation. The elastic band structure, in a spectral representation, is constituted of two branches corresponding to symmetric and antisymmetric modes. In the directional representation, the antisymmetric states of the elastic waves possess a plane wave orbital part and a 4x1 spinor part. Two of the components of the spinor part of the wave function relate to the amplitude of the forward component of waves propagating in both chains. The other two components relate to the amplitude of the backward component of waves. The 4x1 spinorial state of the two coupled chains is supported by the tensor product Hilbert space of two identical subsystems composed of a non-interacting chain with linear springs coupled to a rigid substrate. The 4x1 spinor of the coupled system is shown to be in general not separable into the tensor product of the two 2x1 spinors of the uncoupled subsystems in the directional representation. (C) 2017 Author(s). All article content, except where otherwise noted, is licensed under a Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
32
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
33
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.
34
Galarneau, André. "STAR/GSG domain proteins bind to bipartite RNA motifs." Thesis, McGill University, 2008. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=18718.
Full textAbstract:
Understanding the molecular biology of cells is a central field of research that is essential to all of the biological sciences. Messenger RNAs are the central link between DNA information contained in the nucleus and proteins that are synthesized in the cell cytoplasm. These mRNAs are subject to a substantial amount of modification and control, which are handled or under the supervision of RNA binding proteins. RNA binding proteins are trans-acting factors that interact with cis-acting elements present in the RNA sequence. They play major roles in mRNA processing including alternative splicing, translation, trafficking, localization and non-sense mediated decay. The STAR (signal tranduction activator of RNA metabolism) protein family are RNA binding proteins that can play multiple roles in RNA processing. This family of protein includes among others Quaking (QKI), SRC associated in mitosis (SAM68), SAM68-like mammalian protein 1 (SLM-1) and 2 (SLM-2), splicing factor 1 (SF1), germ-line development (GLD-1). All these family members contain a STAR/GSG domain that embeds a hnRNP K homology domain responsible for conferring the RNA binding properties. Because of the lack of genetic data providing insight about their physiological RNA targets, the function of these RNA binding proteins has been difficult to elucidate. Only a few mRNA targets are known across the whole family of STAR proteins. The hypothesis is that STAR proteins bind to a subset of determined mRNAs, and that identifying these RNAs and understanding how STAR proteins act on them would provide important evidence toward understanding the function of this familly of RNA binding proteins. Using systematic evolution of ligands by exponential enrichment (SELEX), we were able to define the QKI response element (QRE) as an hexanucleotide sequence (ACUAAY) with an additional half-site (UAAY). The identification of a refined QRE allowed us to perform a bioinformatic search which led us to the identification ofBien comprendre la biologie moléculaire de la cellule est un champ de recherche central et essentiel à toutes les sciences biologiques. L'ARN messager est le lien central entre l'information de l'ADN contenu dans le noyau cellulaire et les protéines traduits dans le cytoplasme des cellules. Ces ARN messagers sont sujets à une quantité importante de modifications et de contrôle par des protéines liant l'ARN. Ces protéines jouent plusieurs rôles majeurs dans la maturation des ARN messagers incluant l'épissage alternatif, la traduction, le transport, la localisation ainsi que la dégénérescence d'ARN non-sens. La famille de protéine STAR « Signal Transduction and Activatior of RNA metabolism » sont des protéines liant l'ARN capable de jouer plusieurs rôles dans la maturation des ARNs. Cette famille de protéine comprend Quaking, SAM68, SLM-1, -2, SF1, GLD-1 et plusieurs autres. Tous les membres de cette famille ont au sein de leur structure un domaine STAR/GSG comprenant un plus petit domaine homologue à celui de hnRNP K conférant les propriétés de liaison à l'ARN. Les rôles exactes de cette famille de protéine sont encore difficiles à identifier étant donné le manque de donnés génétiques sur les cibles d'ARN messagers physiologiques dont nous avons en notre possession. En fait, seulement quelques cibles d'ARN messagers ont été identifiées au sein de toute la famille de protéine STAR. L'hypothèse derrière cette étude est que les protéines STAR s'associent avec certains ARN messagers définis et que l'identification de ces ARN messagers et la compréhension sur la façon dont les protéines STAR agissent sur ces derniers fournira des informations pertinentes quant à l'identification exacte du rôle que cette famille de protéines joue dans la cellule. En utilisant une technique de biologie moléculaire appelé SELEX « Systematic Evolution of Ligand by EXponential enrichment », nous avons pu identifier l'élément de réponse l
35
Archer, Adrian Avery. "McDowell, Gettier, and the bipartite account of perceptual knowledge /." St Andrews, 2008. http://hdl.handle.net/10023/511.
Full text
36
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
37
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
38
Schmidt, Harry. "Thermal and nonthermal properties of closed bipartite quantum systems." [S.l. : s.n.], 2007. http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-32382.
Full text
39
Brunstrom, Anna Karin. "A bipartite model of distributed systems: Possibilities and implications." W&M ScholarWorks, 1996. https://scholarworks.wm.edu/etd/1539623877.
Full textAbstract:
Networking software is generally designed in layers. User processes exist at the application layer. They rely on the transport layer to provide them with end-to-end communication. In the distributed systems literature communication is traditionally viewed from the application layer. at the application layer we have no knowledge of the whereabouts of a message once a send operation is completed. at the transport layer, on the other hand, information about the delivery of a message to the transport layer in the receiving host is often available. We believe transport layer information can be better utilized in distributed systems design. This dissertation presents support for this thesis.;We first develop a bipartite system model that allows us to reason formally about transport layer information. We can then propagate transport layer information to the application layer in a formally sound fashion. We define two constructs, delivered and delivered-all, for this purpose. The constructs allow easy implementation of message ordering protocols at the user level. We develop user-level implementations of both causally ordered communication and flush channels.;We also consider the impact of transport layer information on vector time. Transport layer vector time can improve both the computational efficiency and the accuracy of results for certain algorithms. Transport layer vector time also provides the possibility of updating vector time for acknowledgment messages. A distributed termination detection algorithm that takes advantage of this possibility is designed.;Finally, we provide a prototype implementation and associated experimental results. We design and implement a transport layer protocol with support for the delivered and delivered-all constructs. Our flush channel implementation is also included in the prototype system. Our experimental results verify the feasibility of our implementation and show practical evidence in support of the usefulness of transport layer information.
40
Shurbevski, Aleksandar. "An Approximation Framework for Sequencing Problems with Bipartite Structure." 京都大学 (Kyoto University), 2014. http://hdl.handle.net/2433/192221.
Full text
41
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.
42
Brito, Daniel, Gladys Lárez, and Pedro Mago. "La menor suma de grados que conduce a sucesiones potencialmente Pk- bipartitas gráficas." Pontificia Universidad Católica del Perú, 2014. http://repositorio.pucp.edu.pe/index/handle/123456789/96404.
Full textAbstract:
Un grafo bipartito balanceado tiene la propiedad Pk si contiene un subgrafo bipartito balanceado completo de orden 2k, y una sucesión П= (Пx, Пy) es potencialmente Pk - bipartita gráfica si tiene una realización con la propiedad Pk· Sea σ(k, 2n) la menor suma de grados tal que toda sucesión bipartita gráfica П de 2n términos sin ceros y con suma de grados σ(П) ≥ σ(k, 2n) es potencialmente Pk - bipartita gráfica. En este artículo se conjetura que σ(k, 2n) = 2(k- 1)(2n- k)+ 2k, y se prueba que esto es cierto para k = 2 y 3.
43
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
44
Awais, Hussein Sani. "Bipartite edge coloring approach for designing parallel hardware interleaver architecture." Phd thesis, Université de Bretagne Sud, 2012. http://tel.archives-ouvertes.fr/tel-00790045.
Full textAbstract:
Nowadays, Turbo and LDPC codes are two families of codes that are extensively used in current communication standards due to their excellent error correction capabilities. However, hardware design of coders and decoders for high data rate applications is not a straightforward process. For high data rates, decoders are implemented on parallel architectures in which more than one processing elements decode the received data. To achieve high memory bandwidth, the main memory is divided into smaller memory banks so that multiple data values can be fetched from or stored to memory concurrently. However, due to scrambling caused by interleaving law, this parallelization results in communication or memory access conflicts which occur when multiple data values are fetched from or stored in the same memory bank at the same time. This problem is called Memory conflict Problem. It increases latency of memory accesses due to the presence of conflict management mechanisms in communication network and unfortunately decreases system throughput while augmenting system cost. To tackle the memory conflict problems, three different types of approaches are used in literature. In first type of approaches, different algorithms to construct conflict free interleaving law are proposed. The main reason to develop these techniques is to construct "architecture friendly" codes with good error correction capabilities in order to reduce hardware cost. However, architectural constraints applied during code design may impede error correction performance of the codes. In a second type of approaches, different design innovations are introduced to tackle memory conflict problem. Flexible and scalable interconnection network with sufficient path diversity and additional storing elements are introduced to handle memory conflicts. However, flexible networks require large silicon area and cost. In addition, delay introduced due to conflict management mechanisms degrades the maximum throughput and makes these approaches inefficient for high data rate and low power applications. In third type of approaches deals with algorithms that assign data in memory in such a manner that all the processing elements can access memory banks concurrently without any conflict. The benefit of this technique is that decoder implementation does not need any specific network and extra storage elements to support particular interleaving law. However, till now no algorithm exists that can solve memory mapping problem for both turbo and LDPC codes in polynomial time. The work presented in this thesis belongs to the last type of approaches. We propose several methods based on graph theory to solve memory mapping problem for both turbo and LDPC codes. Different formal models based on bipartite and tripartite graphs along with different algorithms to color the edges of these graphs are detailed. The complete path we followed before it is possible to solve mapping problem in polynomial time is hence presented. For the first two approaches, mapping problem is modeled as bipartite graph and then each graph is divided into different sub-graphs in order to facilitate the coloring of the edges. First approach deals with Turbo codes and uses transportation problem algorithms to divide and color the bipartite graph. It can find memory mapping that supports particular interconnection network if the interleaving rule of the application allows it. Second approach solves memory mapping problem for LDPC codes using two different complex algorithms to partition and color each partition. In the third algorithm, each time instance and edge is divided into two parts to model our problem as tripartite graph. Tripartite graph is partitioned into different sub-graphs by using an algorithm based on divide and conquer strategy. Then each subgraph is colored individually by using a simple algorithm to find a conflict free memory mapping for both Turbo and LDPC codes. Finally, in the last approach tripartite graph is transformed into bipartite graph on which coloring algorithm based on Euler partitioning principle is applied to find memory mapping in polynomial time. Several experiments have been performed using interleaving laws coming from different communication standards to show the interest of the proposed mapping methods. All the experiments have been done by using a software tool we developed. This tool first finds conflict free memory mapping and then generates VHDL files that can be synthesized to design complete architecture i.e. network, memory banks and associated controllers. In first experiment, bit interleaver used in Ultra Wide Band (UWB) interleaver is considered and a barrel shifter is used as constraint to design the interconnection network. Results are compared regarding area and runtime with state of the art solutions. In second experiments, a turbo interleaving law defined in High Speed Packet Access (HSPA) standard is used as test case. Memory mapping problems have been solved and associated architectures have been generated for this interleaving law which is not conflict free for any type of parallelism used in turbo decoding. Results are compared with techniques used in state of the art in terms of runtime and area. Third experiment focuses on LDPC. First, last algorithm we proposed is used to find conflict free memory mapping for non-binary LDPC codes defined in the DaVinci Codes FP7 ICT European project. Then, conflict free memory mapping have also been found for partially parallel architecture of LDPC codes used in WiMAX and WiFi for different level of parallelism. It is shown that the proposed algorithm can be used to map data in memory banks for any structured codes used in current and future standards for partially parallel architecture. In last experiment, thanks to the proposed approach we explored the design space of Quadratic Permutation Polynomial (QPP) interleaver that is used in 3GPP-LTE standard. The QPP interleaver is maximum contention-free i.e., for every window size W which is a factor of the interleaver length N, the interleaver is contention free. However, when trellis and recursive units parallelism are also included in each SISO, QPP interleaver is no more contention-free. Results highlight tradeoffs between area and performances based on for different radixes, parallelisms, scheduling (replica versus butterfly)...
45
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).
46
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
47
TSUI, WANYUN, and 崔婉筠. "RANDOM WALK IN BIPARTITE GRAPH." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/49777650378065309751.
Full text
48
Lai, Shang-Hsin, and 賴尚欣. "Extremal K_2,2-free Bipartite Graphs." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/33821141122754321285.
Full textAbstract:
碩士淡江大學
中等學校教師在職進修數學教學碩士學位班
100
An extremal K_2,2-free bipartite graphs is a bipartite graph which contains the maximum number of edges and does not contain any subgraph K_2,2. If this bipartite graph is a subgraph of K_m,n, then finding the number of edges of the extremal bipartite graph is the well-known Zarankiewicz Problem. In this thesis, we let f(m,n) be the number of edges of the extremal K_2,2-free bipartite graph which is a subgraph of K_m,n. We obtain the following results: ①f(m,n)≤n/2+√(mn(m-1)+n^2/4) ②If ≥(m|2), then f(m,n)=(m|2)+n. ③If m≡1,3 (mod 6), then K_m decompose into (m(m-1))/6 edge-disjoint K_3 subgraphs, and f(m,n)=(m|2). ④If ((m|2))/3≤n≤(m|2), then f(m,n)=[((m|2)+3n)/2] . ⑤If m≡1,4 (mod 12), then K_m decompose into (m(m-1))/12 edge-disjoint K_4 subgraphs, and f(m,n)=2(m|2)/3.
49
Shen, Chun-Mei, and 沈春梅. "Extremal K_2,3-free Bipartite Graphs." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/72828031609305254745.
Full textAbstract:
碩士淡江大學
中等學校教師在職進修數學教學碩士學位班
100
An extremal K_2,2-free bipartite graphs is a bipartite graph which contains the maximum number of edges and does not contain any subgraph K_2,2 . If this bipartite graph is a subgraph of K_m,n, then finding the number of edges of the extremal bipartite graph is the well-known Zarankiewicz Problem . In this thesis , we let be the number of edges of the extremal K_2,3-free bipartite graph which is a subgraph of K_m,n .We obtain some results.
50
Che-ShuLee and 李哲旭. "Finer Characterizations ofPure Bipartite Entanglement." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/67499570806696160815.
Full textAbstract:
碩士國立成功大學
物理學系碩博士班
100
A new criterion necessary and sufficient for the separability of pure bipartite systems for arbitrary finite dimensions is demonstrated; and the corresponding finer quantitative measures or characterizations of entanglement (beyond mere separability or nonseparability determination) are discussed. Based on this criterion, we proved that the well-known Peres-Horodecki positivity-of-partial-transform criterion is also necessary and sufficient for separability in the case of pure bipartite systems. The maximum value of entanglement, and the corresponding maximally-entangled states are also worked out in detail.