Knocking Out P_k-free Graphs

Johnson, M.; Paulusma, D.; Stewart, A.

doi:10.1007/978-3-662-44465-8_34

All Outputs (2)

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.