9,247 research outputs found
Decomposing Berge graphs
No full textA hole in a graph is an induced cycle on at least four vertices. A graph is Berge if it has no old hole and if its complement has no odd hole. In 2002, Chudnovsky, Robertson, Seymour and Thomas proved a decomposition theorem for Berge graphs saying that every Berge graph either is in a well understood basic class or has some kind of decomposition. Then, Chudnovsky proved a stronger theorem by restricting the allowed decompositions and another theorem where some decompositions were restricted while other decompositions were extended. We prove here a theorem stronger than all those previously known results. Our proof uses at an essential step one of the theorems of Chudnovsky.Perfect graph ; Berge graph ; 2-join ; even skew partition ; decomposition.
A new decomposition theorem for Berge graphs
No full textA hole in a graph is an induced cycle on at least four vertices. A graph is Berge if it has no odd hole and if its complement has no odd hole. In 2002, Chudnovsky, Robertson, Seymour and Thomas proved a decomposition theorem for Berge graphs saying that every Berge graph either is in a well understood basic class or has some kind of decomposition. Then, Chudnovsky proved a stronger theorem by restricting the allowed decompositions. We prove here a stronger theorem by restricting again the allowed decompositions. Motivation for this new theorem will be given in a work in preparation.Graph, Berge, decomposition, 2-join, skew partition.
Decomposing Berge graphs and detecting balanced skew partitions
No full textWe prove that the problem of deciding whether a graph has a balanced skew partition is NP-hard. We give an O(n9)-time algorithm for the same problem restricted to Berge graphs. Our algorithm is not constructive : it certifies that a graph has a balanced skew partition if it has one. It relies on a new decomposition theorem for Berge graphs, that is more precise than the previously known theorems and implies them easily. Our theorem also implies that every Berge graph can be decomposed in a first step by using only balanced skew partitions, and in a second step by using only 2-joins. Our proof of this new theorem uses at an essential step one of the decomposition theorems of Chudnovsky.Perfect graph, Berge graph, 2-join, balanced skew partition, decomposition, detection, recognition.
How to play the games? Nash versus Berge behavior rules
No full textSocial interactions regularly lead to mutually beneficial transactions that are sometimes puzzling. The prisoner’s dilemma and the chicken and trust games prove to be less perplexing than Nash equilibrium predicts. Moral preferences seem to complement self-oriented motivations and their relative predominance in games is found to vary according to the individuals, their environment, and the game. This paper examines the appropriateness of Berge equilibrium to study several 2×2 game situations, notably cooperative games where mutual support yields socially better outcomes. We consider the Berge behavior rule complementarily to Nash: individuals play one behavior rule or another, depending on the game situation. We then define non-cooperative Berge equilibrium, discuss what it means to play in this fashion, and argue why individuals may choose to do so. Finally, we discuss the relationship between Nash and Berge notions and analyze the rationale of individuals playing in a situational perspective.
Strong Berge and Pareto Equilibrium Existence for a Noncooperative Game
No full textIn this paper, we study the main properties of the strong Berge equilibrium which is also a Pareto efficient (SBPE) and the strong Nash equilibrium (SNE). We prove that any SBPE is also a SNE, we prove also existence theorem of SBPE based on the KyFan inequality. Finally, we also provide a method for computing SPBE.Strong Berge equilibrium, Pareto efficiency, strong Nash equilibrium, Ky Fan inequality
Berge Metrics
No full textTitle: Berge Metrics, Author: Sandra Gregov, Location: ThodeWe consider a number of generalizations of the following question originally
posed by Claude Berge in 1966. Let Sn denote the set of all strings made of [n/2]
white coins and [n/2] black coins. Berge asked what is the minimum number of
moves required to sort an alternating string of Sn by taking 2 adjacent coins to
2 adjacent vacant positions on a one-dimensional board of infinite length such
that the sorted string has all white coins immediately followed by all black
coins (or visa versa). We survey and present results dealing with the first generalization of Berge
sorting which allows Berge k-moves, i.e., taking k adjacent coins to k adjacent
vacant positions. We then explore a further generalization which asks for any
pair of strings in Sn what is the minimum number of Berge k-moves needed
to transform one string into the other. This induces a natural metric on the
set Sn called the Berge k-metric. We examine bounds for the diameter of Sn
allowing Berge k-moves. In particular, we present lower and upper bounds
for Berge 1-metric and explore some aspects of Berge 2-metric along with
computational results.ThesisMaster of Science (MS
P\'osa-type results for Berge-hypergraphs
No full textA Berge cycle of length in a hypergraph is a sequence of
distinct vertices and hyperedges such that
for all , indices taken modulo . F\"uredi,
Kostochka and Luo recently gave sharp Dirac-type minimum degree conditions that
force non-uniform hypergraphs to have Hamiltonian Berge cycles. We give a sharp
P\'osa-type lower bound for -uniform and non-uniform hypergraphs that force
Hamiltonian Berge cycles
Phippsia Stebbing 1906
No full textPhippsia Stebbing Aspidopleurus Sars, 1891: 203 (homonym, Pisces). Phippsia Stebbing, 1906: 89 (new name). Phippsia.–Berge & Vader, 2000: 150 (revision). Type species. Stegocephalus gibbosus Sars, 1883. Included species. Phippsia angustipalpa Berge & Vader, 2000; P. dampieri Berge & Vader, 2000; P. gibbosa (Sars, 1883), P. roemeri Schellenberg, 1925, P. unihamata Berge & Vader, 2000; P. vanhoeffeni (Schellenberg, 1926). Species found in the area. Phippsia angustipalpa Berge & Vader, 2000, P. dampieri Berge & Vader, 2000 and P. vanhoeffeni (Schellenberg, 1926). Remarks. For a revision of Phippsia, and details about the species, see Berge & Vader, 2000.Published as part of Jørgen Berge, 2003, Stegocephalidae (Crustacea: Amphipoda) from Australia and New Zealand, With Descriptions of Eight New Species, pp. 85-112 in Records of the Australian Museum 55 on page 10
ON BERGE EQUILIBRIUM
No full textBased on the notion of equilibrium of a coalition P relatively to a coalition K, of Berge, Zhukovskii has introduced Berge equilibrium as an alternative solution to Nash equilibrium for non cooperative games in normal form. The essential advantage of this equilibrium is that it does not require negotiation of any player with the remaining players, which is not the case when a game has more than one Nashequilibrium. The problem of existence of Berge equilibrium is more difficult (compared to that of Nash). This paper is a contribution to the problem of existence and computation of Berge equilibrium of a non cooperative game. Indeed, using the g-maximum equality, we establish the existence of a Berge equilibrium of a non-cooperative game in normal form. In addition, we give sufficient conditions for theexistence of a Berge equilibrium which is also a Nash equilibrium. This allows us to get equilibria enjoying the properties of both concepts of solution. Finally, using these results, we provide two methods for the computation of Berge equilibria: the first one computes Berge equilibria; the second one computes Berge equilibria which are also Nash equilibria
ON BERGE EQUILIBRIUM
No full textBased on the notion of equilibrium of a coalition P relatively to a coalition K, of Berge, Zhukovskii has introduced Berge equilibrium as an alternative solution to Nash equilibrium for non cooperative games in normal form. The essential advantage of this equilibrium is that it does not require negotiation of any player with the remaining players, which is not the case when a game has more than one Nashequilibrium. The problem of existence of Berge equilibrium is more difficult (compared to that of Nash). This paper is a contribution to the problem of existence and computation of Berge equilibrium of a non cooperative game. Indeed, using the g-maximum equality, we establish the existence of a Berge equilibrium of a non-cooperative game in normal form. In addition, we give sufficient conditions for theexistence of a Berge equilibrium which is also a Nash equilibrium. This allows us to get equilibria enjoying the properties of both concepts of solution. Finally, using these results, we provide two methods for the computation of Berge equilibria: the first one computes Berge equilibria; the second one computes Berge equilibria which are also Nash equilibria
- …
