Critical node cut parameterized by treewidth and solution size is W[1]-hard

DOI10.1007/978-3-319-68705-6_3MaRDI QIDQ1687900zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad

Publication date 4 January 2018

Full work available at URL https://doi.org/10.1007/978-3-319-68705-6_3

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Parameterized complexity of critical node cuts
• Parameterized complexity of critical node cuts
• Cutting up is hard to do: the parameterised complexity of k-cut and related problems
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

Cited in

(4)

• On critical node problems with vulnerable vertices
• Parameterized complexity of critical node cuts
• Parameterized complexity of critical node cuts
• On critical node problems with vulnerable vertices

This page was built for publication: Critical node cut parameterized by treewidth and solution size is \(W[1]\)-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1687900)