Output details

The computational complexity of graph contractions I: polynomially solvable and NP-complete cases.

<12>This paper initiated computational research into graph-contractibility; cited by, e.g., its follow-up: van't Hof, Kaminski, Paulusma, Szeider, Thilikos, On graph contractions and induced minors, DAM 160 (2012) 799-809; a restriction to a graph class: Kaminski, Paulusma, Thilikos, Contractions of planar graphs in polynomial time, ESA2010, 122-133; and a graph editing variant: Heggernes, van't Hof, Lokshtanov, Paul, Obtaining a bipartite graph by contracting few edges, SIDMA (to appear). It won, together with its companion "Levin, Paulusma, Woeginger, The computational complexity of graph contractions II, Networks 52 (2008) 32-56", the Glover-Klingman Prize awarded by Networks for the best paper published in 2008.