Publications related to Exploring unknown environments

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.

Ramsey-Turan numbers for semi-algebraic graphs

János Pach

A semi-algebraic graph G = (V, E) is a graph where the vertices are points in R-d, and the edge set E is defined by a semi-algebraic relation of constant complexity on V. In this note, we establish the following Ramsey-Turan theorem: for every integer p >= ...

ELECTRONIC JOURNAL OF COMBINATORICS2018

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

Compiling Questions into Balanced Quizzes about Documents

Robert West, Cristina Menghini

In the educational framework, knowledge assessment is a critical component, and quizzes (sets of questions with concise answers) are a popular tool for this purpose. This paper focuses on the generation of balanced quizzes, i.e., quizzes that relate to a g ...

ASSOC COMPUTING MACHINERY2018

Graph Heat Mixture Model Learning

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic

Graph inference methods have recently attracted a great interest from the scientific community, due to the large value they bring in data interpretation and analysis. However, most of the available state-of-the-art methods focus on scenarios where all avai ...

IEEE2018

Coordination of Dynamic Software Components with JavaBIP

Simon Bliudze, Anastasia Mavridou

JavaBIP allows the coordination of software components by clearly separating the functional and coordination aspects of the system behavior. JavaBIP implements the principles of the BIP component framework rooted in rigorous operational semantics. Recent w ...

Springer International Publishing2017

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

Infectious Disease Containment Based on a Wireless Sensor System

Marcel Salathé, Xiao Sun

Infectious diseases pose a serious threat to public health due to its high infectivity and potentially high mortality. One of the most effective ways to protect people from being infected by these diseases is through vaccination. However, due to various re ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Removing and Adding Edges for the Traveling Salesman Problem

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a d ...

Assoc Computing Machinery2016

Exploring unknown environments

Graph Chatbot

Chat with Graph Search

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Ramsey-Turan numbers for semi-algebraic graphs

Testing Graph Clusterability: Algorithms and Lower Bounds

Compiling Questions into Balanced Quizzes about Documents

Graph Heat Mixture Model Learning

Coordination of Dynamic Software Components with JavaBIP

Independence number of generalized Petersen graphs

Infectious Disease Containment Based on a Wireless Sensor System

Removing and Adding Edges for the Traveling Salesman Problem

Introducing dynamicity in JavaBIP

Coordination of Dynamic Software Components with JavaBIP

Introducing dynamicity in JavaBIP

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Testing Graph Clusterability: Algorithms and Lower Bounds

Compiling Questions into Balanced Quizzes about Documents

Ramsey-Turan numbers for semi-algebraic graphs

Infectious Disease Containment Based on a Wireless Sensor System

Removing and Adding Edges for the Traveling Salesman Problem

Independence number of generalized Petersen graphs

Graph Heat Mixture Model Learning