Minimization and parameterized variants of vertex partition problems on graphs

DOI10.4230/lipics.isaac.2020.40OpenAlexW3114042964MaRDI QIDQ6087212

Xiao Zhou, Takehiro Ito, Yuma Tamura

Publication date: 14 November 2023

Full work available at URL: https://doi.org/10.4230/lipics.isaac.2020.40

zbMATH Keywords

graph algorithmsfixed-parameter tractabilityapproximabilityfeedback vertex set problemvertex partition problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On parameterized independent feedback vertex set
• FPT algorithms for connected feedback vertex set
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Finding small separators in linear time via treewidth reduction
• Wheel-Free Deletion Is W[2-Hard]
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• The complexity of satisfiability problems
• Approximability of the independent feedback vertex set problem for bipartite graphs
• An improved FPT algorithm for independent feedback vertex set

This page was built for publication: Minimization and parameterized variants of vertex partition problems on graphs