3,072 research outputs found
Solving vertex coloring problems as maximum weight stable set problems
No full textInternational audienceIn Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set Problems on an associated graph. We exploit the transformation proposed by Cornaz and Jost (2008), where given a graph GG, an auxiliary graph View the MathML sourceGˆ is constructed, such that the family of all stable sets of View the MathML sourceGˆ is in one-to-one correspondence with the family of all feasible colorings of GG. The transformation in Cornaz and Jost (2008) was originally proposed for the classical Vertex Coloring and the Max-Coloring problems; we extend it to the Equitable Coloring Problem and the Bin Packing Problem with Conflicts. We discuss the relation between the Maximum Weight Stable formulation and a polynomial-size formulation for the VCP, proposed by Campêlo et al. (2008) and called the Representative formulation. We report extensive computational experiments on benchmark instances of the four problems, and compare the solution method with the state-of-the-art algorithms. By exploiting the proposed method, we largely outperform the state-of-the-art algorithm for the Max-coloring Problem, and we are able to solve, for the first time to proven optimality, 14 Max-coloring and 2 Equitable Coloring instances
Contrasting activity profile of two distributed cortical networks as a function of attentional demands
No full textThe original publication is available at http://www.jneurosci.orgThis work was supported by R01 grant MH-073610 from the National Institutes of Health to Denis Paré
The sandwich line-graph
No full textWe observe that View the MathML source for any graph G with n vertices, where View the MathML source is any acyclic orientation of G and where View the MathML source is the (complement of the) auxiliary line graph introduced in [Cornaz, D., and Jost, V., A one-to-one correspondence between colorings and stable sets, Operations Research Letters 36 (2008), 673–676]. (Where as usual, ω and χ denote the clique number and the chromatic number.) It follows that, for any graph parameter β(G) sandwiched between ω(G) and χ(G), then View the MathML source is sandwiched between ω(G) and χ(G) too. Numerical experiments show that Φtheta is closer to χ than theta, where theta is Lovász theta functionou
Kemeny Elections with Bounded Single-peaked or Single-crossing Width
No full textThis paper is devoted to complexity results re-garding specific measures of proximity to single-peakedness and single-crossingness, called “single-peaked width ” [Cornaz et al., 2012] and “single-crossing width”. Thanks to the use of the PQ-tree data structure [Booth and Lueker, 1976], we show that both problems are polynomial time solvable in the general case (while it was only known for single-peaked width and in the case of narcissistic preferences). Furthermore, we establish one of the first results (to our knowledge) concerning the ef-fect of nearly single-peaked electorates on the com-plexity of an NP-hard voting system, namely we show the fixed-parameter tractability of Kemeny elections with respect to the parameters “single-peaked width ” and “single-crossing width”.
Kemeny Elections with Bounded Single-peaked or Single-crossing Width
No full textInternational audienceThis paper is devoted to complexity results regarding specific measures of proximity to single-peakedness and single-crossingness, called "single-peaked width" [Cornaz et al., 2012] and "single-crossing width". Thanks to the use of the PQ-tree data structure [Booth and Lueker, 1976], we show that both problems are polynomial time solvable in the general case (while it was only known for single-peaked width and in the case of narcissistic preferences). Furthermore, we establish one of the first results (to our knowledge) concerning the effect of nearly single-peaked electorates on the complexity of an NP-hard voting system, namely we show the fixed-parameter tractability of Kemeny elections with respect to the parameters "single-peaked width" and "single-crossing width"
Is Tolerance Political? An Interview with Denis Lacorne
No full textcontribution à un site webDenis Lacorne is the author of "The Limits of Tolerance. Enlightenment Values and Religious Fanaticism" (Columbia University Press, 2019), the English translation of "Les limites de la tolérance" (Gallimard, awarded the Prix Montyon by the Académie Française). In his book, which is intellectually very inspiring because of the many questions it addresses and raises, Denis Lacorne traces the emergence of the notion of tolerance from its early thinkers to the Age of Enlightenment and finally questions the notion and its various understandings through more recent events in France and the United States. What is tolerance? Is tolerance political? Interview by Miriam Périer, CER
Timing of impulses from the central amygdala and bed nucleus of the stria terminalis to the brainstem
No full textThe amygdala and bed nucleus of the stria terminalis (BNST) are thought to subserve distinct functions with the former mediating rapid fear responses to discrete sensory cues and the latter longer “anxiety-like” states in response to diffuse environmental contingencies. Yet, these structures are reciprocally connected and their projection sites overlap extensively. To shed light on the significance of BNST-amygdala connections, we compared the antidromic response latencies of BNST and central amygdala (CE) neurons to brainstem stimulation. Whereas the frequency distribution of latencies was unimodal in BNST neurons (~10 ms mode), that of CE neurons was bimodal (~10 and ~30 ms modes). However, after stria terminalis (ST) lesions, only short-latency antidromic responses were observed, suggesting that CE axons with long conduction times course through the ST. Compared to the direct route, the ST greatly lengthens the path of CE axons to the brainstem, an apparently disadvantageous arrangement. Since BNST and CE share major excitatory basolateral amygdala (BL) inputs, lengthening the path of CE axons might allow synchronization of BNST and CE impulses to brainstem when activated by BL. To test this, we applied electrical BL stimuli and compared orthodromic response latencies in CE and BNST neurons. The latency difference between CE and BNST neurons to BL stimuli approximated that seen between the antidromic responses of BNST cells and CE neurons with long-conduction times. These results point to a hitherto unsuspected level of temporal coordination between the inputs and outputs of CE and BNST neurons, supporting the idea of shared functions.The original publication is available at: http://jn.physiology.org/cgi/content/full/100/6/342
On co-bicliques
No full textA co-biclique of a simple undirected graph G = (V,E) is the edge-set of two disjoint complete subgraphs of G.
(A co-biclique is the complement of a biclique.)
A subset F ⊆ E is an independent of G if there is a co-biclique B such that F ⊆ B, otherwise F is a dependent of G. This paper describes the minimal dependents of G. (A minimal dependent is a dependent C such that any proper subset of C is an independent.)
It is showed that a minimum-cost dependent set of G can be determined in polynomial time for any nonnegative cost vector . Based on this, we obtain a branch-and-cut algorithm for the maximum co-biclique problem which is, given a weight vector , to find a co-biclique B of G maximizing w(B) = ∑e∈B we
Max-multiflow/min-multicut for G+H series-parallel
No full textAbstractWe give a new characterization of series-parallel graphs which implies that the maximum integer multiflow is equal to the minimum capacity multicut if G+H is series-parallel, where G+H denotes the union of the support graph G and the demand graph H.We investigate the difference between a result of the type “the cut-condition is sufficient for the existence of a multiflow in some class” and a result of the type “max-multiflow = min-multicut for some class”
Rehab Depot de la Plaine Saint-Denis
No full textRedesign for workshop Atelier Revision Intermediaire at the Depot de la Plaine Saint-Denis with a rehabilitation center as new functionRMITArchitecture and The Built Environmen
- …
