Solving partition problems almost always requires pushing many vertices around

DOI10.1137/19M1239362MaRDI QIDQ5220192zbMATH OpenFDO

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)

Full work available at URL https://doi.org/10.1137/19M1239362

zbMATH Keywords

graph partitioningmonopolar graphspolynomial kernel

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3977053 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• More about subcolorings
• On 2-Subcolourings of Chordal Graphs
• On the computational complexity of (O,P)-partition problems
• On the parameterized complexity of multiple-interval graph problems
• On the Polarity and Monopolarity of Graphs
• 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 almost always requires pushing many vertices around
• 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

(3)

• Cluster deletion on interval graphs and split related graphs
• Solving partition problems almost always requires pushing many vertices around
• Faster algorithms for graph monopolarity

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)