Split contraction: the untold story

DOI10.1145/3319909MaRDI QIDQ5205814zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3319909

zbMATH Keywords

edge contractionparameterized complexitysplit contractionsplit graphs

Mathematics Subject Classification ID

Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 6862097
• Obtaining split graphs by edge contraction
• Obtaining split graphs by edge contraction
• On the parameterized approximability of contraction to classes of chordal graphs
• Contraction Blockers for Graphs with Forbidden Induced Paths

Cited in

(16)

• Parameterized analysis and crossing minimization problems
• On the parameterized complexity of grid contraction
• A single exponential-time FPT algorithm for cactus contraction
• scientific article; zbMATH DE number 6862097 (Why is no real title available?)
• On the parameterized approximability of contraction to classes of chordal graphs
• Obtaining split graphs by edge contraction
• Contracting to a longest path in H-free graphs
• On the Parameterized Complexity of Maximum Degree Contraction Problem.
• Reducing the vertex cover number via edge contractions
• Vertex identification to a forest
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
• Metric dimension and geodetic set parameterized by vertex cover
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
• A finer view of the parameterized landscape of labeled graph contractions
• On the parameterized complexity of maximum degree contraction problem
• Obtaining split graphs by edge contraction

This page was built for publication: Split contraction: the untold story

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