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

DOI10.4230/LIPIcs.ISAAC.2017.20zbMath1457.68209OpenAlexW2783263885MaRDI QIDQ5136236

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Exact exponential algorithms.
• A graph coloring algorithm for large scale scheduling problems
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• 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
• On the linear vertex-arboricity of a planar graph
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• A graph coloring algorithm for large scheduling problems
• A graph‐theoretic generalization of the clique concept
• Parameterized Algorithms
• Acyclic colorings of planar graphs