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)
Conference Proceeding
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. M. (2015). Minimal disconnected cuts in planar graphs. In A. Kosowski, & I. Walukiewicz (Eds.), Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, proceedings (243-254). https://doi.org/10.1007/978-3-319-22177-9_19

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)
Conference Proceeding
Johnson, M., Paulusma, D., & Stewart, A. (2014). Knocking Out P_k-free Graphs. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29August 2014 ; proceedings, Part II (396-407). https://doi.org/10.1007/978-3-662-44465-8_34

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.