Publication

Avoiding long Berge cycles: the missing casesk=r+1 andk=r+2

Publications associées (21)

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

Efficient Streaming Subgraph Isomorphism with Graph Neural Networks

Karl Aberer, Quoc Viet Hung Nguyen, Chi Thang Duong, Trung-Dung Hoang

Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do n ...

ASSOC COMPUTING MACHINERY2021

Representing graphs through data with learning and optimal transport

Hermina Petric Maretic

Graphs offer a simple yet meaningful representation of relationships between data. This representation is often used in machine learning algorithms in order to incorporate structural or geometric information about data. However, it can also be used in an i ...

EPFL2021

Fast and Accurate Efficient Streaming Subgraph Isomorphism

Karl Aberer, Quoc Viet Hung Nguyen, Chi Thang Duong, Trung-Dung Hoang

2020

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

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

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

Optimal Classification In Sparse Gaussian Graphic Model

Zhigang Yao, Yingying Fan

Consider a two-class classification problem where the number of features is much larger than the sample size. The features are masked by Gaussian noise with mean zero and covariance matrix Sigma, where the precision matrix Omega = Sigma(-1) is unknown but ...

Institute of Mathematical Statistics2013

A Bayesian Method for Matching Two Similar Graphs without Seeds

Matthias Grossglauser, Pedram Pedarsani

Approximate graph matching (AGM) refers to the problem of mapping the vertices of two structurally similar graphs, which has applications in social networks, computer vision, chemistry, and biology. Given its computational cost, AGM has mostly been limited ...

2013

Intersection Patterns of Edges in Topological Graphs

Radoslav Fulek

This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossi ...

EPFL2012

Adjacent Crossings Do Matter

Radoslav Fulek

In a drawing of a graph, two edges form an odd pair if they cross each other an odd number of times. A pair of edges is independent if they share no endpoint. For a graph G, let ocr(G) be the smallest number of odd pairs in a drawing of G and let iocr(G) b ...

Springer-Verlag Berlin2011

Split-critical and uniquely split-colorable graphs

Dominique de Werra, Bernard Ries, Tinaz Ekim

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring p ...

2010

k-Edge-Connectivity: Approximation and LP Relaxation

David Pritchard

This paper's focus is the following family of problems, denoted k-ECSS, where k denotes a positive integer: given a graph (V, E) and costs for each edge, find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1 it is the spanning tre ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

Partitioning graphs into complete and empty graphs

Tinaz Ekim

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j + k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j, k)-graph. For a fixed j and k ...

Elsevier2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Dominique de Werra

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...

2009

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit ...

EPFL2008

A graph coloring heuristic using partial solutions and a reactive tabu scheme

Nicolas Zufferey

Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called FOO- ...

2008

Polar cographs

Dominique de Werra, Tinaz Ekim

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite grap ...

Elsevier2008

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

Generalized vertex coloring problems using split graphs

Tinaz Ekim

Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. ...

EPFL2006