Publication

Generalized vertex coloring problems using split graphs

Publications associées (195)

Graph Chatbot

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.

Connectez-vous pour utiliser Chat avec Graph Search

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

The weighted stable matching problem

Linda Farczadi

We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general ...

2017

Learning time varying graphs

Pascal Frossard, Andreas Loukas, Vasilis Kalofolias

We consider the problem of inferring the hidden structure of high-dimensional dynamic systems from the perspective of graph learning. In particular, we aim at capturing the dynamic relationships between nodes by a sequence of graphs. Our approach is motiva ...

Ieee2017

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

A semi-algebraic version of Zarankiewicz's problem

János Pach

A bipartite graph G is semi-algebraic in R-d if its vertices are represented by point sets P,Q subset of R-d and its edges are defined as pairs of points (p,q) epsilon P x Q that satisfy a Boolean combination of a fixed number of polynomial equations and i ...

European Mathematical Soc2017

Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward

Michael Christoph Gastpar, Saeid Sahraei

A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψlog(nψ)) , where ψ=sqrt(P ||h||^2+1) ...

Institute of Electrical and Electronics Engineers2017

Group-Sparse Model Selection: Hardness and Relaxations

Volkan Cevher, Anastasios Kyrillidis, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. The main promise of these models is the recovery of ``interpretable" signals along with ...

Institute of Electrical and Electronics Engineers2016

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

János Pach

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can ...

Springer Basel Ag2016

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016