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

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

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)

Cites Work

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

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)