Improved kernelization and fixed-parameter algorithm for bipartite one-sided vertex explosion

DOI10.1016/J.TCS.2026.116149MaRDI QIDQ7316949zbMATH OpenFDO

Authors Yunlong Liu, Guang Xiao, Ao Liu, Di Wu, Jingui Huang

Publication date 21 August 2026

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

Full work available at URL https://doi.org/10.1016/J.TCS.2026.116149

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• An FPT algorithm for bipartite vertex splitting
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• Automated generation of search tree algorithms for hard graphs modification problems
• Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
• Edge crossings in drawings of bipartite graphs
• Edge deletion problems: branching facilitated by modular decomposition
• Faster algorithm for pathwidth one vertex deletion
• scientific article; zbMATH DE number 512967 (Why is no real title available?)
• Improved analysis of highest-degree branching for feedback vertex set
• Obtaining a Planar Graph by Vertex Deletion
• Parameterized algorithms for planar 2-layer drawing by vertex splitting on a given subset
• Parameterized complexity of vertex splitting to pathwidth at most 1
• Planarizing graphs and their drawings by vertex splitting
• Two-Layer Planarization: Improving on Parameterized Algorithmics

This page was built for publication: Improved kernelization and fixed-parameter algorithm for bipartite one-sided vertex explosion

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