Publications related to Characterizing Path Graphs by Forbidden Induced Subgraphs

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.

Scaling a Reliable Distributed System

Alexandre David Olivier Maurer

We consider the problem of reliably connecting an arbitrarily large set of computers (nodes) with communication channels. Reliability means here the ability, for any two nodes, to remain connected (i.e., their ability to communicate) with probability at le ...

LPD EPFL2016

Vertex-Frequency Analysis on Graphs

Pierre Vandergheynst, Benjamin Ricaud, David Shuman

One of the key challenges in the area of signal processing on graphs is to design dictionaries and transform methods to identify and exploit structure in signals on weighted graphs. To do so, we need to account for the intrinsic geometric structure of the ...

Academic Press Inc Elsevier Science2016

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

Enhanced Matrix Completion with Manifold Learning

Pierre Vandergheynst, Michael Bronstein, Xavier Bresson, Vasilis Kalofolias

We study the problem of matrix completion when infor- mation about row or column proximities is available, in the form of weighted graphs. The problem can be formulated as the optimization of a convex function that can be solved efficiently using the alter ...

2015

Coloring Relatives of Interval Overlap Graphs via On-line Games

Bartosz Maria Walczak

The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...

Springer-Verlag Berlin2014

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

Triangle-free intersection graphs of line segments with large chromatic number

Bartosz Maria Walczak, Michal Lason

In the 1970s Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k we construct a triangle-free fam ...

Academic Press Inc Elsevier Science2014

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Bartosz Maria Walczak, Michal Lason

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...

Springer2014

Characterizing Path Graphs by Forbidden Induced Subgraphs

Graph Chatbot

Chat with Graph Search

Simple topological graphs

Scaling a Reliable Distributed System

Vertex-Frequency Analysis on Graphs

Removing and Adding Edges for the Traveling Salesman Problem

Reconstruction of Images from Gabor Graphs with Applications in Facial Image Processing

Enhanced Matrix Completion with Manifold Learning

Coloring Relatives of Interval Overlap Graphs via On-line Games

Two notions of unit distance graphs

Triangle-free intersection graphs of line segments with large chromatic number

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Simple topological graphs

Scaling a Reliable Distributed System

Removing and Adding Edges for the Traveling Salesman Problem

Vertex-Frequency Analysis on Graphs

Enhanced Matrix Completion with Manifold Learning

Reconstruction of Images from Gabor Graphs with Applications in Facial Image Processing

Coloring Relatives of Interval Overlap Graphs via On-line Games

Triangle-free intersection graphs of line segments with large chromatic number

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Two notions of unit distance graphs