Minimization and parameterized variants of vertex partition problems on graphs

DOI10.4230/LIPICS.ISAAC.2020.40MaRDI QIDQ6087212zbMATH OpenOpenAlexFDO

Authors Yuma Tamura, Takehiro Ito, Xiao Zhou

Publication date 14 November 2023

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

zbMATH Keywords

approximabilityfeedback vertex set problemfixed-parameter tractabilitygraph algorithmsvertex partition problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• On vertex partitions and some minor-monotone graph parameters
• Graph Bipartization and via minimization
• scientific article; zbMATH DE number 524137
• Graph partitions with minimum degree constraints
• Vertex partitioning problems on graphs with bounded tree width
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation Algorithms for the Minimum Convex Partition Problem
• An extremal problem for vertex partition of complete multipartite graphs

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A parameterized complexity view on collapsing \(k\)-cores
• An improved FPT algorithm for independent feedback vertex set
• Approximability of the independent feedback vertex set problem for bipartite graphs
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Finding small separators in linear time via treewidth reduction
• FPT algorithms for connected feedback vertex set
• scientific article; zbMATH DE number 2159638 (Why is no real title available?)
• scientific article; zbMATH DE number 7650230 (Why is no real title available?)
• On parameterized independent feedback vertex set
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• The complexity of satisfiability problems
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Wheel-Free Deletion Is W[2]-Hard

Cited in

(5)

• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• Solution of one problem of optimal partition of the vertex set of a hypergraph
• A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem
• Min-Max Graph Partitioning and Small Set Expansion
• Complexity of near-3-choosability problem

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

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