Algorithms for partition of some class of graphs under compaction and vertex-compaction

DOI10.1007/s00453-012-9720-9zbMath1275.05057OpenAlexW2023673835MaRDI QIDQ378212

Narayan Vikas

Publication date: 11 November 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9720-9

zbMATH Keywords

computational complexitygraphretractionhomomorphismcoloringpolynomial time algorithmsvertex partitioncompactionvertex-compaction

Mathematics Subject Classification ID

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)

Related Items

Unnamed Item, Disconnected cuts in claw-free graphs, The Complexity of Boolean Surjective General-Valued CSPs, The computational complexity of disconnected cut and \(2 K_2\)-partition, Surjective \(H\)-colouring: new hardness results, Computational complexity relationship between compaction, vertex-compaction, and retraction, The Complexity of Counting Surjective Homomorphisms and Compactions, Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of compaction to irreflexive cycles
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Polynomial graph-colorings
• Consistency in networks of relations
• Networks of constraints: Fundamental properties and applications to picture processing
• List homomorphisms and circular arc graphs
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Complexity of graph partition problems
• Algorithms for Partition of Some Class of Graphs under Compaction
• List Partitions
• Compaction, Retraction, and Constraint Satisfaction
• Computing and Combinatorics
• Computational Complexity of Compaction to Reflexive Cycles
• Duality and Polynomial Testing of Tree Homomorphisms