56 citations · 270 across the 25 of their papers we have counts for
10 papers · 1 filter
Maximum independent sets in (pyramid, even hole)-free graphs
Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon +1
A \emph{hole} in a graph is an induced cycle with at least 4 vertices. A graph is \emph{even-hole-free} if it does not contain a hole on an even number of vertices. A \emph{pyramid…
Counting weighted independent sets beyond the permanent
Martin Dyer, Mark Jerrum, Haiko Muller +1
Jerrum, Sinclair and Vigoda (2004) showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition…
Structure and algorithms for (cap, even hole)-free graphs
Kathie Cameron, Murilo V. G. da Silva, Shenwei Huang +1
A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with…
On rank-width of even-hole-free graphs
Isolde Adler, Ngoc Khang Le, Haiko Müller +3
We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because cho…
Parameterized algorithm for weighted independent set problem in bull-free graphs
Stéphan Thomassé, Nicolas Trotignon, Kristina Vusković
The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph…
Graphs that do not contain a cycle with a node that has at least two neighbors on it
Pierre Aboulker, Marko Radovanović, Nicolas Trotignon +1
We recall several known results about minimally 2-connected graphs, and show that they all follow from a decomposition theorem. Starting from an analogy with critically 2-connected…
Combinatorial optimization with 2-joins
Nicolas Trotignon, Kristina Vušković
A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs.…
Algorithms for square--free Berge graphs
Frédéric Maffray, Nicolas Trotignon, Kristina Vušković
We consider the class of graphs containing no odd hole, no odd antihole, and no configuration consisting of three paths between two nodes such that any two of the paths induce a ho…
Coloring perfect graphs with no balanced skew-partitions
Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck +1
We present an algorithm that computes a maximum stable set of any perfect graph with no balanced skew-partition. We present time algorithm that colors them.
Vertex elimination orderings for hereditary graph classes
Pierre Aboulker, Pierre Charbit, Nicolas Trotignon +1
We provide a general method to prove the existence and compute efficiently elimination orderings in graphs. Our method relies on several tools that were known before, but that were…