The Complexity of the List Partition Problem for Graphs

DOI10.1137/060666238MaRDI QIDQ3544241zbMATH OpenOpenAlexFDO

Authors Kathie Cameron, Elaine M. Eschen, R. Sritharan, Chính T. Hoàng

Publication date 5 December 2008

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

Full work available at URL https://researchrepository.wvu.edu/faculty_publications/364

zbMATH Keywords

algorithmcomplexitygraph partitionlist partition

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The list partition problem for graphs
• List Partitions
• Two algorithms for general list matrix partitions
• Complexity of graph partition problems
• Generalized partitions of graphs

Cited in

(33)

• NP-hard and linear variants of hypergraph partitioning
• Generalized partitions of graphs
• The monotonicity property of \(M\)-partition problems
• \(2K_2\)-partition of some classes of graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Dichotomy for tree-structured trigraph list homomorphism problems
• Partitioning a graph into disjoint cliques and a triangle-free graph
• An efficiently solvable graph partition problem to which many problems are reducible
• Graph partitions with prescribed patterns
• Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
• Complexity of graph partition problems
• Graph partitions: recent progresses and some open problems
• Two algorithms for general list matrix partitions
• Minimal disconnected cuts in planar graphs
• Algorithms to approximately count and sample conforming colorings of graphs
• A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more)
• The parameterised complexity of list problems on graphs of bounded treewidth
• 2K2-Partition Problem
• 2K2 vertex-set partition into nonempty parts
• Obstructions to partitions of chordal graphs
• Clique versus independent set
• scientific article; zbMATH DE number 1161313 (Why is no real title available?)
• List monopolar partitions of claw-free graphs
• The complexity of surjective homomorphism problems-a survey
• Solving partition problems almost always requires pushing many vertices around
• The external constraint 4 nonempty part sandwich problem
• The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem
• The list partition problem for graphs
• Parameterizing cut sets in a graph by the number of their components
• Digraph matrix partitions and trigraph homomorphisms
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• \(2K_{2}\) vertex-set partition into nonempty parts

This page was built for publication: The Complexity of the List Partition Problem for Graphs

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