Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1

DOI10.1007/978-3-031-43380-1_3MaRDI QIDQ6496541

Ignaz Rutter, Unnamed Author, Unnamed Author

Publication date: 3 May 2024

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• 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
• Planarizing graphs and their drawings by vertex splitting
• An FPT algorithm for bipartite vertex splitting

This page was built for publication: Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1