12 citations · 76 across the 20 of their papers we have counts for
3 papers · 1 filter
Max Weight Independent Set in sparse graphs with no long claws
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +2
We revisit the recent polynomial-time algorithm for the MAX WEIGHT INDEPENDENT SET (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component i…
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +1
For graphs and , we say that is -free if it does not contain as an induced subgraph. Already in the early 1980s Alekseev observed that if is connected, then t…
Induced subgraphs of bounded treewidth and the container method
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk +2
A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By we denote a path on vertices. In this paper we give polynomial-…