Perfeziona i miei risultati

Lingua

Domaine

Public access from 9-lug-2021
Université de Fribourg

Detecting strong cliques

Hujdurovic, Ademir ; Milanic, Martin ; Ries, Bernard

In: Discrete Mathematics, 2019, vol. 342, no. 9, p. 2738-2750

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely...

Université de Fribourg

Bicolored Matchings in Some Classes of Graphs

Costa, Marie-Christine ; de Werra, Dominique ; Picouleau, Christophe ; Ries, Bernard

In: Graphs and Combinatorics, 2007, vol. 23, no. 1, p. 47-60

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R| = n + 1 such that perfect matchings with k red edges exist for all k, 0 ≤ k ≤ n. Given two integers p...

Université de Fribourg

On a graph coloring problem arising from discrete tomography

Bentz, Cédric ; Costa, Marie-Christine ; de Werra, Dominique ; Picouleau, Christophe ; Ries, Bernard

In: Networks, 2008, vol. 51, no. 4, p. 256-267

An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family equation image of chains Pi together with vectors h(Pi) = (h1, . . . , hik), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = hij. An interpretation in terms of scheduling is presented. We consider special cases of...

Université de Fribourg

Degree-constrained edge partitioning in graphs arising from discrete tomography

Bentz, Cédric ; Costa, Marie-Christine ; Picouleau, Christophe ; Ries, Bernard ; de Werra, Dominique

In: Journal of Graph Algorithms and Applications, 2009, vol. 13, no. 2, p. 99-118

Starting from the basic problem of reconstructing a 2-dimensional im- age given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k = 3 colors is open. Variations and special cases are considered for the case k = 3 colors where the graph corresponding to the union of some color classes (for instance colors 1...

Université de Fribourg

Claw-free graphs with strongly perfect complements : Fractional and integral version, Part II: Nontrivial strip-structures

Chudnovsky, Maria ; Ries, Bernard ; Zwols, Yori

In: Discrete applied mathematics, 2011, vol. 159, no. 17, p. 1996-2029

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the...

Université de Fribourg

A note on chromatic properties of threshold graphs

Ries, Bernard ; de Werra, Dominique ; Zenklusen, Rico

In: Discrete Mathematics, 2012, vol. 312, no. 10, p. 1838-1843

In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a similar question about vertex colorings: given an integer p, when is it possible to find weights (in general depending on p) for the vertices and...

Université de Neuchâtel

Scalable content-based publish/suscribe and application to online trading

Barazzutti, Raphaël P. ; Felber, Pascal (Dir.)

Thèse de doctorat : Université de Neuchâtel, 2019.

Publish/subscribe is a popular messaging pattern that provides efficient and decoupled information dissemination in distributed environments. Publishers generate a flow of information as publications, which are routed to subscribers based on their interests expressed as subscriptions. Matching events against filters has a non-negligible processing cost. Our first contribution within this...

Università della Svizzera italiana

Quality control mechanisms of protein biogenesis : proteostasis dies hard

Bergmann, Timothy Jan ; Brambilla Pisoni, Giorgia ; Molinari, Maurizio

In: AIMS biophysics, 2016, vol. 3, no. 4, p. 456-478

The biosynthesis of proteins entails a complex series of chemical reactions that transform the information stored in the nucleic acid sequence into a polypeptide chain that needs to properly fold and reach its functional location in or outside the cell. It is of no surprise that errors might occur that alter the polypeptide sequence leading to a non-functional proteins or that impede delivery...

Università della Svizzera italiana

Post ER quality control : a role for UDP-glucose : glycoprotein glucosyl transferase and p97

Fregno, Ilaria ; Molinari, Maurizio

In: Journal of rare diseases research & treatment, 2016, vol. 1, no. 1, p. 40-42

Human proteinopathies are diseases caused by the expression of defective gene products. In some cases, these diseases involve the degradation of mutant but otherwise functional proteins by the quality control system of the secretory pathway. Our recent study identified two proteins that play a role in post-endoplasmic reticulum (ER) quality control and are potential targets for therapeutic ...

Université de Fribourg

Claw-free graphs with strongly perfect complements : Fractional and integral version. Part I. Basic graphs

Chudnovsky, Maria ; Ries, Bernard ; Zwols, Yori

In: Discrete Applied Mathematics, 2011, vol. 159, no. 17, p. 1971-1995

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the...