Graphe biparti complet

Résumé

En théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble. Plus précisément, il existe une partition de son ensemble de sommets en deux sous-ensembles U et V telle que chaque sommet de U est relié à chaque sommet de V. Si le premier ensemble U est de cardinal m et le second ensemble V est de cardinal n, le graphe biparti complet est noté K_{m,n}. Exemples Étoiles Si m = 1, le graphe complet biparti K1,n est une étoile et est noté S_n. upright=2.63|thumb|center|Les étoiles S3, S4, S5 et S6. En particulier, les étoiles sont des arbres. D'ailleurs, tous les graphes bipartis complets qui sont des arbres sont des étoiles. Autres exemples Voici des exemples pour m = 3. Image:Complete bipartite graph K3,1.svg|''K

Source officielle

https://fr.wikipedia.org/wiki/Graphe_biparti_complet

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (27)

Publications associées

Chargement

Personnes associées (3)

Personnes associées

Chargement

Unités associées (2)

Unités associées

Chargement

Concepts associés (25)

Concepts associés

Chargement

Cours associés (5)

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many domains.

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpected (and sometimes paradoxical) properties for which no other methods of construction are known.

Students will learn the core concepts and techniques of network analysis with emphasis on causal inference. Theory and application will be balanced, with students working directly with network data throughout the course.

Afficher plus

Cours associés

Chargement

Séances de cours associées (14)

Séances de cours associées

Chargement

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delta - 1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with Delta = O(log n), and they conjectured the existence of online algorithms using Delta (1+o(1)) colors for Delta = omega(log n). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS'03 and Bahmani et al., SODA'10). We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))Delta-edge-coloring algorithm for Delta = omega(log n) known a priori. Surprisingly, if Delta is not known ahead of time, we show that no (e/e-1 - Omega(1)) Delta-edge-coloring algorithm exists. We then provide an optimal, (e/e-1 + o(1))Delta-edge-coloring algorithm for unknown Delta = omega(log n). To obtain our results, we study a nonstandard fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.

IEEE COMPUTER SOC2019

Chargement

The weighted stable matching problem

Linda Farczadi

We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general. Our contribution is two fold: a polyhedral characterization and an approximation algorithm. Previously Chen et al. have shown that the stable matching polytope is integral if and only if the subgraph obtained after running phase one of Irving's algorithm is bipartite. We improve upon this result by showing that there are instances where this subgraph might not be bipartite but one can further eliminate some edges and arrive at a bipartite subgraph. Our elimination procedure ensures that the set of stable matchings remains the same, and thus the stable matching polytope of the final subgraph contains the incidence vectors of all stable matchings of our original graph. This allows us to characterize a larger class of instances for which the weighted stable matching problem is polynomial-time solvable. We also show that our edge elimination procedure is best possible, meaning that if the subgraph we arrive at is not bipartite, then there is no bipartite subgraph that has the same set of stable matchings as the original graph. We complement these results with a 2-approximation algorithm for the minimum weight stable matching problem for instances where each agent has at most two possible partners in any stable matching. This is the first approximation result for any class of instances with general weights.

2017

Chargement

Online Matching with General Arrivals

Buddhima Ruwanmini Gamlath Gamlath Ralalage, Mikhail Kapralov, Andreas Maggiori, Ola Nils Anders Svensson, David Wajc

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following. 1) For edge arrivals, randomization does not help no randomized algorithm is better than 1/2 competitive. 2) For general vertex arrivals, randomization helps - there exists a randomized (1/2+Omega (1))-competitive online matching algorithm.

IEEE COMPUTER SOC2019

Chargement