Publications related to Partitioning graphs into complete and empty graphs

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.

On Simplices in Diameter Graphs in R-4

Andrei Kupavskii

A graph G is a diameter graph in R-d if its vertex set is a finite subset in R-d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in R-4 contains the complete subgraph K on five vertices, then any ...

Maik Nauka/Interperiodica/Springer2017

Spinner: Scalable Graph Partitioning in the Cloud

Andreas Loukas, Dionysios Logothetis

In this paper, we present a graph partitioning algorithm to partition graphs with trillions of edges. To achieve such scale, our solution leverages the vertex-centric Pregel abstraction provided by Giraph, a system for large-scale graph analytics. We desig ...

Ieee2017

On the Difficulty of Selecting Ising Models with Approximate Recovery

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt an approximate recovery criterion that allows for a number of missed edges ...

Ieee-Inst Electrical Electronics Engineers Inc2016

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?

Matthias Grossglauser, Ehsan Kazemi, Lyudmila Yartseva

Network alignment refers to the problem of matching the vertex sets of two unlabeled graphs, which can be viewed as a generalization of the classic graph isomorphism problem. Network alignment has applications in several fields, including social network an ...

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

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

Homometric sets in trees

Radoslav Fulek, Slobodan Mitrovic

Let G = (V, E) denote a simple graph with vertex set V and edge set E. The profile of a vertex set V' subset of V denotes the multiset of pairwise distances between the vertices of V'. Two disjoint subsets of V are homometric if their profiles are the same ...

Academic Press Ltd- Elsevier Science Ltd2014

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

On the Performance of Percolation Graph Matching

Matthias Grossglauser, Lyudmila Yartseva

Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and in ...

ACM2013

Partitioning graphs into complete and empty graphs

Graph Chatbot

Chat with Graph Search

On Simplices in Diameter Graphs in R-4

Spinner: Scalable Graph Partitioning in the Cloud

On the Difficulty of Selecting Ising Models with Approximate Recovery

A Precise Threshold For Quasi-Ramsey Numbers

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?

Coloring Relatives of Interval Overlap Graphs via On-line Games

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

Homometric sets in trees

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

On the Performance of Percolation Graph Matching

On Simplices in Diameter Graphs in R-4

On the Difficulty of Selecting Ising Models with Approximate Recovery

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

Spinner: Scalable Graph Partitioning in the Cloud

Coloring Relatives of Interval Overlap Graphs via On-line Games

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Homometric sets in trees

A Precise Threshold For Quasi-Ramsey Numbers

On the Performance of Percolation Graph Matching