Parameterized complexity of vertex splitting to pathwidth at most 1

DOI10.1016/J.TCS.2024.114928MaRDI QIDQ6639742

[[Person:6496540|Author name not available (Why is that?)]], [[Person:6075932|Author name not available (Why is that?)]], Ignaz Rutter

Publication date: 18 November 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

algorithmscomputational complexitygraphskernelizationvertex splittingbranching algorithmfixed-parameterized tractability2-layer drawingpathwidth 1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The node-deletion problem for hereditary properties is NP-complete
• On the planar split thickness of graphs
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• Graph minors. XIII: The disjoint paths problem
• Faster algorithm for pathwidth one vertex deletion
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A 4 k ² kernel for feedback vertex set
• A Quartic Kernel for Pathwidth-One Vertex Deletion
• Easy problems for tree-decomposable graphs
• Obtaining a Planar Graph by Vertex Deletion
• Reducibility among Combinatorial Problems
• Planarity Allowing Few Error Vertices in Linear Time
• A linear time algorithm for finding tree-decompositions of small treewidth
• A Near-Optimal Planarization Algorithm
• Parameterized Algorithms

This page was built for publication: Parameterized complexity of vertex splitting to pathwidth at most 1

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