Concept

Petersen graph

Related publications (199)

Parallelizing Machine Learning- Functionally: A Framework and Abstractions for Parallel Graph Processing

Implementing machine learning algorithms for large data, such as the Web graph and social networks, is challenging. Even though much research has focused on making sequential algorithms more scalable, their running times continue to be prohibitively long. ...

2011

Extraction of network topology from multi-electrode recordings: is there a small-world effect?

Wulfram Gerstner, Joao Emanuel Felipe Gerhard

The simultaneous recording of the activity of many neurons poses challenges for multivariate data analysis. Here, we propose a general scheme of reconstruction of the functional network from spike train recordings. Effective, causal interactions are estima ...

Frontiers Research Foundation2011

Drawing planar graphs of bounded degree with few slopes

János Pach, Balázs Keszegh, Doemoetoer Palvoelgyi

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

Methods for Clustering Multi-Layer Graphs in Mobile Networks

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Clustering on graphs has been studied extensively for years due to its numerous applications. However, in contrast to the classic problems, clustering in mobile and online social networks brings new challenges. In these scenarios, it is common that observa ...

2011

Beyond Graphs: A New Synthesis

Dario Floreano, Claudio Mattiussi, Daniel Marbach, Peter Dürr

Artiﬁcial neural networks, electronic circuits, and gene networks are some examples of systems that can be modeled as networks, that is, as collections of interconnected nodes. In this paper we introduce the concept of terminal graph (t-graph for short), w ...

2011

Complexity of the critical node problem over trees

Marco Di Summa

In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. ...

2011

Graphs that Admit Right Angle Crossing Drawings

Radoslav Fulek, Balázs Keszegh, Filip Moric

We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends pe ...

2010

Algebraic techniques for deterministic networks

Christina Fragouli, Javad Ebrahimi Boroojeni

We here summarize some recent advances in the study of linear deterministic networks, recently proposed as approximations for wireless channels. This work started by extending the algebraic framework developed for multicasting over graphs in [1] to include ...

2010

Hypergraphic LP Relaxations for Steiner Trees

David Pritchard

We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Koenemann et al. [Math. Programming, 2009]. Specifically, we are interested in proving upper bounds on the integrality gap of this ...

Springer2010

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

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.

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010