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

DOI10.1007/978-3-319-68705-6_3zbMATH Open1483.05170OpenAlexW2766259723MaRDI QIDQ1687900FDOQ1687900

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

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

Mathematics Subject Classification ID

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

Cited In (4)

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

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)