An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem

DOI10.4230/LIPICS.ISAAC.2017.20zbMATH Open1457.68209OpenAlexW2783263885MaRDI QIDQ5136236FDOQ5136236

Authors Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Peter Rossmanith

Publication date 25 November 2020

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

zbMATH Keywords

2-plex2-plex bipartitionbounded-degree-1 set bipartitiondefective \((2,1)\)-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Approximation algorithm for the balanced 2-connected bipartition problem
• A fixed parameter algorithm for optimal convex partitions
• A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem
• A 2-approximation for the maximum satisfying bisection problem
• A local search algorithm for binary maximum 2-path partitioning
• An efficient algorithm for the bipartite matching problem
• Approximation algorithm for the balanced 2-connected \(k\)-partition problem
• Approximation algorithms for the maximum bounded connected bipartition problem
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors

Cites work

• scientific article; zbMATH DE number 4134069 (Why is no real title available?)
• scientific article; zbMATH DE number 3979083 (Why is no real title available?)
• scientific article; zbMATH DE number 517057 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• A graph coloring algorithm for large scale scheduling problems
• A graph coloring algorithm for large scheduling problems
• A graph‐theoretic generalization of the clique concept
• Acyclic colorings of planar graphs
• Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Exact exponential algorithms.
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Fundamentals of parameterized complexity
• On the linear vertex-arboricity of a planar graph
• Parameterized algorithms
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(1)

• A modified DIRECT algorithm with bilevel partition

This page was built for publication: An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem

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