Publication

On random subgraphs of Kneser and Schrijver graphs

Publications associées (40)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Joint Power Allocation and Path Selection for Multi-Hop Noncoherent Decode and Forward UWB Communications

Xiaoli Ma, Marco Mondelli, Qi Zhou

With the aim of extending the coverage and improving the performance of impulse radio ultra-wideband (UWB) systems, this paper focuses on developing a novel single differential encoded decode and forward (DF) non-cooperative relaying scheme (NCR). To favor ...

Ieee-Inst Electrical Electronics Engineers Inc2014

A note on chromatic properties of threshold graphs

Dominique de Werra, Bernard Ries, Rico Zenklusen

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 simila ...

2012

Disjoint homometric sets in graphs

János Pach

Two subsets of vertices in a graph are called homometric if the multisets of distances determined by them are the same. Let h(n) denote the largest number h such that any connected graph of n vertices contains two disjoint homometric subsets of size h. It ...

2011

Every graph admits an unambiguous bold drawing

János Pach

Let r and w be a fixed positive numbers, w < r. In a bold drawing of a graph, every vertex is represented by a disk of radius r, and every edge by a narrow rectangle of width w. We solve a problem of van Kreveld [K09] by showing that every graph admits a b ...

Springer-Verlag Berlin2011

MARGIN: Maximal frequent subgraph mining

Ramachandra Satyanarayana Valluri

The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs providing ample scope for pruning. MARGIN is a maximal su ...

2010

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image 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 ...

2009

Graph coloring with cardinality constraints on the neighborhoods

Dominique de Werra, Bernard Ries

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over ...

2009

A Magnetic Procedure for the Stability Number

Dominique de Werra

A magnet is a pair u, v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new verte ...

2009

On the inapproximability of independent domination in 2P3-free perfect graphs

Dominique de Werra

We consider the complexity of approximation for the INDEPENDENT DOMINATING SET problem in 2P(3)-free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as all induced subgraph. We show that, if P not equal ...

2009

Degenerate crossing numbers

János Pach

Let G be a graph with n vertices and ea parts per thousand yen4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p, then they properly cross one another at p. It is shown that the number of crossing points, ...

Springer-Verlag2009