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
Showing 2013 · cs.DMShow all
3 papers · 2 filters
cs.DM2013★ 42 cited
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…
cs.DM2013★ 29 cited
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.…
cs.DM2013★ 10 cited
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.