Concept
Cycle basis
Publications associées (12)
Non-Exponential Variations for Classical Results in First Passage Percolation
We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges.
We start by describing the asymptotic behavior of the diameter and the f ...
EPFL2020Monopulse Beam Synthesis Using a Sparse Single Layer of Weights
A conventional monopulse radar system uses three beams, namely, sum beam, elevation difference beam, and azimuth difference beam, which require different layers of weights to synthesize each beam independently. Since the multilayer structure increases the ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019New Notions and Constructions of Sparsification for Graphs and Hypergraphs
A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...
IEEE COMPUTER SOC2019Time-resolved analysis of dynamic graphs: an extended Slepian design
Dimitri Nestor Alice Van De Ville, Raphaël Pierre Liégeois, Ibrahim Merad
Graphs are extensively used to represent networked data. In many applications, especially when considering large datasets, it is a desirable feature to focus the analysis onto specific subgraphs of interest. Slepian theory and its extension to graphs allow ...
SPIE-INT SOC OPTICAL ENGINEERING2019Are motorways rational from slime mould's point of view ?
We analyse the results of our experimental laboratory approximation of motorways networks with slime mould Physarum polycephalum. Motorway networks of fourteen geographical areas are considered: Australia, Africa, Belgium, Brazil, Canada, China, Germany, I ...
2012Intersection Patterns of Edges in Topological Graphs
This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossi ...
EPFL2012Fast Computation of Small Cuts via Cycle Space Sampling
We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space iden ...
2011Reduced Basis method for parametrized elliptic advection-reaction problems
In this work we consider the Reduced Basis method for the solution of parametrized advection-reaction partial differential equations. For the generation of the basis we adopt a stabilized finite element method and we define the Reduced Basis method in the ...
2010Finding Hamiltonian circuits in quasi-adjoint graphs
Dominique de Werra, Benjamin Leroy-Beaulieu
This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. This paper pr ...
2008Variations of coloring problems related to scheduling and discrete tomography
The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...
EPFL2007