Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1

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

Authors: Ignaz Rutter 

Publication date: 3 May 2024

Mathematics Subject Classification ID

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

Cites Work

• Reducibility among combinatorial problems
• The node-deletion problem for hereditary properties is NP-complete
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A \(4k^2\) kernel for feedback vertex set
• Parameterized algorithms
• A linear time algorithm for finding tree-decompositions of small treewidth
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• Obtaining a Planar Graph by Vertex Deletion
• Planarizing graphs and their drawings by vertex splitting
• Title not available (Why is that?)
• A near-optimal planarization algorithm
• A quartic kernel for pathwidth-one vertex deletion
• Faster algorithm for pathwidth one vertex deletion
• An FPT algorithm for bipartite vertex splitting
• Planarity Allowing Few Error Vertices in Linear Time
• Title not available (Why is that?)

Cited In (2)

• A faster parameterized algorithm for bipartite 1-sided vertex explosion
• Splitting plane graphs to outerplanarity

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 Q6496541)