Publication

On the robustness of the metric dimension of grid graphs to adding a single edge

Related publications (52)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Assembling a Network out of Ambiguous Patches

Matthias Grossglauser, Lyudmila Yartseva, Jefferson Elbert Simões

Many graph mining and network analysis problems rely on the availability of the full network over a set of nodes. But inferring a full network is sometimes non-trivial if the raw data is in the form of many small {\em patches} or subgraphs, of the true net ...

2016

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

Charles Babbage Res Ctr2016

Disjoint edges in topological graphs and the tangled-thrackle conjecture

Andres Jacinto Ruiz Vargas

It is shown that fora constant t is an element of N, every simple topological graph on n vertices has 0(n) edges if the graph has no two sets of t edges such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of th ...

Academic Press Ltd- Elsevier Science Ltd2016

Source Localization on Graphs via l1 Recovery and Spectral Graph Theory

Pierre Vandergheynst, Xavier Bresson, Rodrigo Cerqueira Gonzalez Pena

We cast the problem of source localization on graphs as the simultaneous problem of sparse recovery and diffusion ker- nel learning. An l1 regularization term enforces the sparsity constraint while we recover the sources of diffusion from a single snapshot ...

Ieee2016

Modeling and Controlling epidemics : a graph perspective

Philippe Sakari Rossinelli

The social and economical impact a virus has in a population is not negligible. For this reason, gaining a theoretical understanding of the behavior of a virus is of prime importance. This project is going to be divided in several parts. First, we will dis ...

2015

Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency Frames

Pierre Vandergheynst, David Shuman

We consider the problem of designing spectral graph filters for the construction of dictionaries of atoms that can be used to efficiently represent signals residing on weighted graphs. While the filters used in previous spectral graph wavelet constructions ...

Institute of Electrical and Electronics Engineers2015

Two notions of unit distance graphs

Andrei Kupavskii

A faithful (unit) distance graph in R-d is a graph whose set of vertices is a finite subset of the d-dimensional Euclidean space, where two vertices are adjacent if and only if the Euclidean distance between them is exactly 1. A (unit) distance graph in Rd ...

Academic Press Inc Elsevier Science2014

Diameter Graphs in R-4

Andrei Kupavskii

A diameter graph in is a graph whose set of vertices is a finite subset of and whose set of edges is formed by pairs of vertices that are at diameter apart. This paper is devoted to the study of different extremal properties of diameter graphs in and on a ...

Springer2014

Reversible Sesqui-Pushout Rewriting, Graph Transformation

Sandro Stucki

The paper proposes a variant of sesqui-pushout rewriting (SqPO) that allows one to develop the theory of nested application conditions (NACs) for arbitrary rule spans; this is a considerable generalisation compared with existing results for NACs, which onl ...

Springer2014

A Bayesian Method for Matching Two Similar Graphs without Seeds

Matthias Grossglauser, Pedram Pedarsani

Approximate graph matching (AGM) refers to the problem of mapping the vertices of two structurally similar graphs, which has applications in social networks, computer vision, chemistry, and biology. Given its computational cost, AGM has mostly been limited ...

2013