Solving partition problems almost always requires pushing many vertices around

DOI10.1137/19M1239362zbMATH1434.05123MaRDI QIDQ5220192FDOQ5220192

Authors Christian Komusiewicz, Manuel Sorge, Erik Jan van Leeuwen, Iyad Kanj

Publication date 11 March 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph partitioningpolynomial kernelmonopolar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Planar graph vertex partition for linear problem kernels
• The Complexity of the List Partition Problem for Graphs
• The list partition problem for graphs
• Generalized partitions of graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

Cites work

• scientific article; zbMATH DE number 3977053 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 7378721 (Why is no real title available?)
• A Polynomial Kernel for Proper Interval Vertex Deletion
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Algorithms for unipolar and generalized split graphs
• Complexity and algorithms for recognizing polar and monopolar graphs
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
• Fundamentals of parameterized complexity
• Graph Subcolorings: Complexity and Algorithms
• Graph theory
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• More about subcolorings
• On 2-Subcolourings of Chordal Graphs
• On the Polarity and Monopolarity of Graphs
• On the computational complexity of (O,P)-partition problems
• On the parameterized complexity of multiple-interval graph problems
• Parameterized algorithms
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Parameterized algorithms on perfect graphs for deletion to \((r,\ell)\)-graphs
• Parametrized complexity theory.
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• Recognition of unipolar and generalised split graphs
• Solving partition problems with colour-bipartitions
• Subcolorings and the subchromatic number of a graph
• The algorithm design manual
• The complexity of \(G\)-free colourability
• The complexity of partitioning into disjoint cliques and a triangle-free graph
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

Cited in

(1)

• Cluster deletion on interval graphs and split related graphs

Describes a project that uses

Uses Software

• Stony Brook

This page was built for publication: Solving partition problems almost always requires pushing many vertices around

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