Affiner les résultats


Université de Fribourg

The firefighter problem with more than one firefighter on trees

Bazgan, Cristina ; Chopin, Morgan ; Ries, Bernard

In: Discrete Applied Mathematics, 2013, vol. 161, p. 899-908

In this paper we study the complexity of generalized versions of the firefighter problem on trees, and answer several open questions of Finbow and MacGillivray (2009) [8]. More specifically, we consider the version denoted by Max (S, b)-Fire where b ≥ 2 firefighters are allowed at each time step and the objective is to maximize the number of saved vertices that belong to S. We also study...

Université de Fribourg

Characterizations of cographs as intersection graphs of paths on a grid

Cohen, Elad ; Golumbic, Martin Charles ; Ries, Bernard

In: Discrete Applied Mathematics, 2014, vol. 178, p. 46-57

A cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges (→ B1-EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (→...

Université de Fribourg

On some applications of the selective graph coloring problem

Demange, Marc ; Ekim, Tinaz ; Ries, Bernard ; Tanasescu, Cerasela

In: European Journal of Operational Research, 2015, vol. 240, no. 2, p. 307-314

In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph col-oring problem as well as several of its possible applications. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared...

Université de Fribourg

Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples

Hujdurovic, Ademir ; Kacar, Ursula ; Milanic, Martin ; Ries, Bernard ; Tomescu, Alexandru I.

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, vol. 15, no. 1, p. 96-108

Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number...

Université de Fribourg

A 2-approximation for the maximum satisfying bisection problem

Ries, Bernard ; Zenklusen, Rico

In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169-175

Given a graph G =(V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that |V1| = |V2|, and such that every vertex v in V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is NP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...

Université de Fribourg

Some properties of edge intersection graphs of single-bend paths on a grid

Asinowski, Andrei ; Ries, Bernard

In: Discrete Mathematics, 2012, vol. 312, no. 2, p. 427-440

In this paper we consider graphs G whose vertices can be represented as single-bend paths (i.e., paths with at most one turn) on a rectangular grid, such that two vertices are adjacent in G if and only if the corresponding paths share at least one edge of the grid. These graphs, called B1-EPG graphs, were first introduced in Golumbic et al. (2009) [13]. Here we show that the neighborhood of every...

Université de Fribourg

Colouring vertices of triangle-free graphs without forests

Dabrowski, Konrad K. ; Lozin, Vadim ; Raman, Rajiv ; Ries, Bernard

In: Discrete Mathematics, 2012, vol. 312, no. 7, p. 1372-1385

The vertex colouring problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the vertex colouring problem in subclasses of triangle-free graphs obtained by forbidding graphs without cycles, i.e.,...

Università della Svizzera italiana

Multilevel solution strategies for unfitted finite element methods

Kothari, Hardik ; Krause, Rolf (Dir.)

Thèse de doctorat : Università della Svizzera italiana, 2020 ; 2020INFO009.

In the unfitted finite element methods, traditionally we can use Nitsche's method or the method of Lagrange multipliers to enforce the boundary/interface conditions. In this work, we present tailored multilevel methods for solving the problems stemming from either of these discretizations. Generally, multigrid methods require a hierarchy of finite element (FE) spaces which can be created...

Università della Svizzera italiana

Perspectives on the measurement problem : perspectives from the measurement problem

Hansen, Arne ; Wolf, Stefan (Dir.)

Thèse de doctorat : Università della Svizzera italiana, 2020 ; 2020INFO008.

In quantum mechanics, the measurement problem is commonly regarded as reason for deep concern. It seems that, either, the problem can be solved and there is hope for quantum mechanics, or the theory better be left behind in search of another one. We investigate the prospect of finding a solution to the measurement problem—within quantum mechanics, as well as in theoretical frameworks beyond...

Università della Svizzera italiana

Deep learning for 3D hand biometric systems

Svoboda, Jan ; Bronstein, Michael (Dir.) ; Masci, Jonathan (Codir.)

Thèse de doctorat : Università della Svizzera italiana, 2020 ; 2020INFO007.

Hands are an indispensable part of human bodies used in our everyday life to express ourselves and manipulate the surrounding world. Moreover, a hand contains highly- unique characteristics that allow for distinguishing among different individuals. Though fingerprints are widely-known for this, the hand also has a unique geometric shape, palmprint, and vein structure. The shapes of a hand and...