Concept

Multiple edges

Publications associées (31)

Graph-based image representation learning

Though deep learning (DL) algorithms are very powerful for image processing tasks, they generally require a lot of data to reach their full potential. Furthermore, there is no straightforward way to impose various properties, given by the prior knowledge a ...

EPFL2019

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

On the Rainbow Turan number of paths

Abhishek Methuku

Let F be a fixed graph. The rainbow Turan number of F is defined as the maximum number of edges in a graph on n vertices that has a proper edge-coloring with no rainbow copy of F (i.e., a copy of F all of whose edges have different colours). The systematic ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Christoph Hunkenschröder

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

2019

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

Balázs Keszegh, Abhishek Methuku, Doemoetoer Palvoelgyi

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

COMENIUS UNIV2019

Asyrnptotics for the Turan number of Berge-K-2,K-t

Abhishek Methuku

Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it. ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Graph Heat Mixture Model Learning

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic

Graph inference methods have recently attracted a great interest from the scientific community, due to the large value they bring in data interpretation and analysis. However, most of the available state-of-the-art methods focus on scenarios where all avai ...

IEEE2018

Learning time varying graphs

Pascal Frossard, Ntorina Thanou, 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