60 citations
- Centre National de la Recherche ScientifiqueFR16 papers
- University of LeedsGB16 papers
- Laboratoire de l'Informatique du ParallélismeFR14 papers
- École Normale Supérieure de LyonFR13 papers
- Institut national de recherche en sciences et technologies du numériqueFR6 papers
- Université de LyonFR6 papers
- University of BelgradeRS6 papers
- Laboratoire d'Informatique Algorithmique: Fondements et ApplicationsFR4 papers
- Lyon 1 UniversitéFR4 papers
- Princeton UniversityUS3 papers
- Université Paris DiderotFR2 papers
- University of Novi SadRS2 papers
6 papers · 1 filter
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…
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.…
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…