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)
algorithmscomputational complexitygraphskernelizationvertex splittingbranching algorithmfixed-parameterized tractability2-layer drawingpathwidth 1
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 2 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)
