The computational complexity of disconnected cut and \(2 K_2\)-partition
From MaRDI portal
Publication:2259853
DOI10.1016/j.jctb.2014.09.002zbMath1307.05128MaRDI QIDQ2259853
Daniël Paulusma, Barnaby Martin
Publication date: 5 March 2015
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2014.09.002
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C40: Connectivity
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Unnamed Item, The Complexity of Boolean Surjective General-Valued CSPs, Minimum Violation Vertex Maps and Their Applications to Cut Problems, The Complexity of Counting Surjective Homomorphisms and Compactions, The complexity of contracting bipartite graphs into small cycles, Reducing the vertex cover number via edge contractions, Constraint satisfaction problem: what makes the problem easy, Contracting to a longest path in H-free graphs, On the Parameterized Complexity of Maximum Degree Contraction Problem., Parameterizing cut sets in a graph by the number of their components, Coloring problems on bipartite graphs of small diameter, On the parameterized complexity of maximum degree contraction problem, Surjective \(H\)-colouring: new hardness results, Coherent network partitions, Disconnected cuts in claw-free graphs, Coherent network partitions: characterizations with cographs and prime graphs, A single exponential-time FPT algorithm for cactus contraction, Minimal Disconnected Cuts in Planar Graphs, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- Increasing the minimum degree of a graph by contractions
- The external constraint 4 nonempty part sandwich problem
- Parameterizing cut sets in a graph by the number of their components
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Edge-contraction problems
- \(2K_{2}\) vertex-set partition into nonempty parts
- Covering graphs with few complete bipartite subgraphs
- Partitioning graphs into connected parts
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- An algorithm for finding clique cut-sets
- On stable cutsets in graphs
- \(2K_2\)-partition of some classes of graphs
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- On disconnected cuts and separators
- Contracting graphs to 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
- Algorithms for Partition of Some Class of Graphs under Compaction
- Finding Large Clique Minors is Hard
- Recognizing decomposable graphs
- The Complexity of the List Partition Problem for Graphs
- List Partitions
- Compaction, Retraction, and Constraint Satisfaction
- FindingH-partitions efficiently
- Computational Complexity of Compaction to Reflexive Cycles
- Reducibility among Combinatorial Problems
- Fast Skew Partition Recognition
- Classifying the Complexity of Constraints Using Finite Algebras
- Obtaining a Bipartite Graph by Contracting Few Edges
