Concept

Claw-free graph

Related publications (42)

An algorithmic decomposition of claw-free graphs leading to an O(n^3) algorithm for the weighted stable set problem

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free ...

2011

A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)

Yuri Faenza

We introduce a family of reductions for removing proper and homogeneous pairs of cliques from a graph G. This family generalizes some routines presented in the literature, mostly in the context of claw-free graphs. These reductions can be embedded in a sim ...

2011

Approximating Graphic TSP by Matchings

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leadi ...

IEEE Computer Society2011

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

Network Design via Core Detouring for Problems Without a Core

Thomas Rothvoss

Some of the currently best-known approximation algorithms for network design are based on random sampling. One of the key steps of such algorithms is connecting a set of source nodes to a random subset of them. In a recent work [Eisenbrand,Grandoni,Rothvo\ ...

Springer2010

, ,

A community in a network is a subset of vertices densely connected to each other, but less connected to the vertices outside. Many different approaches have been developed to find such structures in a given network, but the main drawback of most of the ava ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Community detection enhancement in networks using proper weighting and partial synchronization

Martin Hasler, Ali Ajdari Rad, Alireza Khadivi

IEEE2010

Community Detection Enhancement in Networks using Proper Weighting and Partial Synchronization

Martin Hasler, Ali Ajdari Rad, Alireza Khadivi

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Coloring Fuzzy Circular Interval Graphs

Friedrich Eisenbrand, Martin Niemeier

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs ...

Elsevier2009

On the inapproximability of independent domination in 2P3-free perfect graphs

Dominique de Werra

We consider the complexity of approximation for the INDEPENDENT DOMINATING SET problem in 2P(3)-free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as all induced subgraph. We show that, if P not equal ...

2009

Graph Chatbot

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.