Outputs (3)

Knocking out P_k-free graphs (2015)
Journal Article
Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108. https://doi.org/10.1016/j.dam.2015.04.010

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Paralle... Read More about Knocking out P_k-free graphs.

Minimal disconnected cuts in planar graphs (2015)
Presentation / Conference Contribution
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. M. (2015, August). Minimal disconnected cuts in planar graphs. Presented at 20th International Symposium, FCT 2015, Gdańsk, Poland

The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity is not known for planar graph... Read More about Minimal disconnected cuts in planar graphs.

Knocking Out P_k-free Graphs (2014)
Presentation / Conference Contribution
Johnson, M., Paulusma, D., & Stewart, A. (2014, December). Knocking Out P_k-free Graphs. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Paralle... Read More about Knocking Out P_k-free Graphs.