Concept
Claw-free graph
Publications associées (42)
ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS
We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...
Ottawa2023Sublinear Algorithms for Spectral Graph Clustering
This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requir ...
EPFL2021Manycore clique enumeration with fast set intersections
Paolo Ienne, Kubilay Atasu, Radu Ioan Stoica, Jovan Blanusa
Listing all maximal cliques of a given graph has important applications in the analysis of social and biological networks. Parallelisation of maximal clique enumeration (MCE) algorithms on modern manycore processors is challenging due to the task-level par ...
ACM2020Time-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 ENGINEERING2019Weighted Matchings via Unweighted Augmentations
Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage
We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively pa ...
ASSOC COMPUTING MACHINERY2019Finding Perfect Matchings in Bipartite Hypergraphs
Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...
SPRINGER HEIDELBERG2018The gene family-free median of three
Background: The gene family-free framework for comparative genomics aims at providing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We study two problems related to the b ...
2017Removing and Adding Edges for the Traveling Salesman Problem
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a d ...
Assoc Computing Machinery2016Saturated simple and k-simple topological graphs
A simple topological graph G is a graph drawn in the plane so that any pair of edges have at most one point in common, which is either an endpoint or a proper crossing. G is called saturated if no further edge can be added without violating this condition. ...
Elsevier Science Bv2015Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(vertical bar V vertical bar (vertical bar E vertical bar+vertical bar V vertical bar log vertical bar V vertical bar))-time, drastically improvin ...
Assoc Computing Machinery2014