Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1

DOI10.1007/978-3-031-43380-1_3MaRDI QIDQ6496541zbMATH OpenFDO

Authors Ignaz Rutter

Publication date 3 May 2024

Mathematics Subject Classification ID

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

Cites work

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

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)