Complexity of graph partition problems
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) 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)
Recommendations
Cited in
(52)- Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces
- On the complexity of partitioning graphs into connected subgraphs
- On the complexity of assembly partitioning
- On stable cutsets in graphs
- Structured proportional representation
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- Partitioning chordal graphs into independent sets and cliques
- Stable skew partition problem
- On decision and optimization (\(k\),\(l\))-graph sandwich problems
- On the complexity of cd-coloring of graphs
- The complexity of dissociation set problems in graphs
- One-three join: a graph operation and its consequences
- Forbidden lifts (NP and CSP for combinatorialists)
- A graph clustering algorithm based on a clustering coefficient for weighted graphs
- Extended skew partition problem
- Fixed-parameter algorithms for the cocoloring problem
- On the sum-max graph partitioning problem
- On the minimum monochromatic or multicolored subgraph partition problems
- On realizations of point determining graphs, and obstructions to full homomorphisms
- Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- The cd-coloring of graphs
- Many Facets of Dualities
- Clique cycle-transversals in distance-hereditary graphs
- Counting 4 4 matrix partitions of graphs
- scientific article; zbMATH DE number 5005081 (Why is no real title available?)
- On the structure of self-complementary graphs
- 2K2-Partition Problem
- Characterizing –partitionable Cographs
- NP for Combinatorialists
- The Complexity of the List Partition Problem for Graphs
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- Clique versus independent set
- scientific article; zbMATH DE number 1161313 (Why is no real title available?)
- scientific article; zbMATH DE number 1512686 (Why is no real title available?)
- Factorizations and characterizations of induced‐hereditary and compositive properties
- FindingH-partitions efficiently
- Communication complexity of pairs of graph families with applications
- Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
- Fast Skew Partition Recognition
- The list partition problem for graphs
- Computational complexity relationship between compaction, vertex-compaction, and retraction
- Partitioning a graph into complementary subgraphs
- Partitioning problems in dense hypergraphs
- On the complexity of coloring ‐graphs
- Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
- Computing the partition function for graph homomorphisms
- Rainbow graph splitting
- Packing \(r\)-cliques in weighted chordal graphs
- List matrix partitions of chordal graphs
- Digraph matrix partitions and trigraph homomorphisms
- Polarity of chordal graphs
This page was built for publication: Complexity of graph partition problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819579)
