Publications associées à Generalized vertex coloring problems using split graphs

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Local Approximation of the Maximum Cut in Regular Graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

Time-resolved analysis of dynamic graphs: an extended Slepian design

Dimitri Nestor Alice Van De Ville, Raphaël Pierre Liégeois, Ibrahim Merad

Graphs are extensively used to represent networked data. In many applications, especially when considering large datasets, it is a desirable feature to focus the analysis onto specific subgraphs of interest. Slepian theory and its extension to graphs allow ...

SPIE-INT SOC OPTICAL ENGINEERING2019

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Negar Kiyavash, Saber Salehkaleybar, Kun Zhang

A directed acyclic graph (DAG) is the most common graphical model for representing causal relationships among a set of variables. When restricted to using only observational data, the structure of the ground truth DAG is identifiable only up to Markov equi ...

AAAI Press2019

Thrackles: An improved upper bound

János Pach, Radoslav Fulek

A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, ex ...

ELSEVIER SCIENCE BV2019

Extended Formulations from Communication Protocols in Output-Efficient Time

Yuri Faenza, Manuel Francesco Aprile

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the exten ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

An Optimal Space Lower Bound for Approximating MAX-CUT

Mikhail Kapralov

We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output hal ...

ASSOC COMPUTING MACHINERY2019

Online Matching with General Arrivals

Ola Nils Anders Svensson, Mikhail Kapralov, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomi ...

IEEE COMPUTER SOC2019

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov, John Michael Goddard Kallaugher

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...

IEEE COMPUTER SOC2018

Generalized vertex coloring problems using split graphs

Graph Chatbot

Chattez avec Graph Search

Local Approximation of the Maximum Cut in Regular Graphs

Time-resolved analysis of dynamic graphs: an extended Slepian design

On the Turan number of ordered forests

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Thrackles: An improved upper bound

Extended Formulations from Communication Protocols in Output-Efficient Time

An Optimal Space Lower Bound for Approximating MAX-CUT

Online Matching with General Arrivals

Incidences Between Planes Over Finite Fields

The Sketching Complexity of Graph and Hypergraph Counting

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

On the Turan number of ordered forests

Extended Formulations from Communication Protocols in Output-Efficient Time

Local Approximation of the Maximum Cut in Regular Graphs

Time-resolved analysis of dynamic graphs: an extended Slepian design

Thrackles: An improved upper bound

An Optimal Space Lower Bound for Approximating MAX-CUT

Online Matching with General Arrivals

Incidences Between Planes Over Finite Fields

The Sketching Complexity of Graph and Hypergraph Counting