Complexity of graph partition problems

DOI10.1145/301250.301373zbMath1345.68171OpenAlexW2036185209MaRDI QIDQ2819579

Sulamita Klein, Tomás Feder, Pavol Hell

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301250.301373

Mathematics Subject Classification ID

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

Related Items (39)

One-three join: a graph operation and its consequences ⋮ Stable skew partition problem ⋮ On decision and optimization (\(k\),\(l\))-graph sandwich problems ⋮ Clique cycle-transversals in distance-hereditary graphs ⋮ Counting \(4 \times 4\) matrix partitions of graphs ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ On the complexity of cd-coloring of graphs ⋮ Structured proportional representation ⋮ NP for Combinatorialists ⋮ On the complexity of coloring ‐graphs ⋮ Forbidden lifts (NP and CSP for combinatorialists) ⋮ Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques ⋮ A graph clustering algorithm based on a clustering coefficient for weighted graphs ⋮ Extended skew partition problem ⋮ Many Facets of Dualities ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ On the sum-max graph partitioning problem ⋮ On the minimum monochromatic or multicolored subgraph partition problems ⋮ Polarity of chordal graphs ⋮ On realizations of point determining graphs, and obstructions to full homomorphisms ⋮ Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees ⋮ Partitioning a graph into complementary subgraphs ⋮ Factorizations and characterizations of induced‐hereditary and compositive properties ⋮ FindingH-partitions efficiently ⋮ Rainbow graph splitting ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ The cd-Coloring of Graphs ⋮ Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces ⋮ Partitioning chordal graphs into independent sets and cliques ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon ⋮ Communication Complexity of Pairs of Graph Families with Applications ⋮ On stable cutsets in graphs ⋮ A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results ⋮ On the structure of self-complementary graphs ⋮ 2K2-Partition Problem ⋮ Characterizing –partitionable Cographs ⋮ Packing \(r\)-cliques in weighted chordal graphs ⋮ List matrix partitions of chordal graphs

This page was built for publication: Complexity of graph partition problems