Solving partition problems almost always requires pushing many vertices around

DOI10.1137/19M1239362zbMATH Open1434.05123MaRDI QIDQ5220192FDOQ5220192

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

Publication date: 11 March 2020

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

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

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)

Cites Work

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

Cited In (1)

• Cluster deletion on interval graphs and split related graphs

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)