Publications related to Improved Ramsey-type results for comparability 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.

Distributed Diffusion Adaptation Over Graph Signals

Ali H. Sayed, Jie Chen, Roula Nassif

Most works on graph signal processing assume static graph signals, which is a limitation even in comparison to traditional DSP techniques where signals are modeled as sequences that evolve over time. For broader applicability, it is necessary to develop te ...

IEEE2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Slobodan Mitrovic, Mohsen Ghaffari

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...

ASSOC COMPUTING MACHINERY2018

Execution Trace Graph of Dataflow Process Networks

Marco Mattavelli, Simone Casale Brunet

The paper introduces and specifies a formalism that provides complete representations of dataflow process network (DPN) program executions, by means of directed acyclic graphs. Such graphs, also known as execution trace graphs (ETG), are composed of nodes ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2018

Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition

Dominique de Werra

In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. We also present the first constructive polynomial-time algorithm for the recognition of 3-letter graphs. ...

SPRINGER INTERNATIONAL PUBLISHING AG2018

Filtering Random Graph Processes Over Random Time-Varying Graphs

Andreas Loukas

Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochasticity i ...

Institute of Electrical and Electronics Engineers2017

Geometric Graph Matching Using Monte Carlo Tree Search

Pascal Fua, Jan Kybic, Miguel Amável Dos Santos Pinheiro

We present an efficient matching method for generalized geometric graphs. Such graphs consist of vertices in space connected by curves and can represent many real world structures such as road networks in remote sensing, or vessel networks in medical imagi ...

Ieee Computer Soc2017

Extension complexity of stable set polytopes of bipartite graphs

Yuri Faenza, Manuel Francesco Aprile

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

Springer2017

Diverse M-Best Solutions by Dynamic Programming

Michaël Unser, Virginie Sophie Uhlmann

Many computer vision pipelines involve dynamic programming primitives such as finding a shortest path or the minimum energy solution in a tree-shaped probabilistic graphical model. In such cases, extracting not merely the best, but the set of M-best soluti ...

Springer2017

Improved Ramsey-type results for comparability graphs

Graph Chatbot

Chat with Graph Search

Distributed Diffusion Adaptation Over Graph Signals

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Execution Trace Graph of Dataflow Process Networks

Scalable analysis of linear networked systems via chordal decomposition

Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition

Filtering Random Graph Processes Over Random Time-Varying Graphs

Geometric Graph Matching Using Monte Carlo Tree Search

Extension complexity of stable set polytopes of bipartite graphs

Exploring Selection Bias by Causal Frailty Models

Diverse M-Best Solutions by Dynamic Programming

Filtering Random Graph Processes Over Random Time-Varying Graphs

Execution Trace Graph of Dataflow Process Networks

Geometric Graph Matching Using Monte Carlo Tree Search

Exploring Selection Bias by Causal Frailty Models

Diverse M-Best Solutions by Dynamic Programming

Distributed Diffusion Adaptation Over Graph Signals

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Scalable analysis of linear networked systems via chordal decomposition

Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition

Extension complexity of stable set polytopes of bipartite graphs