Computational complexity relationship between compaction, vertex-compaction, and retraction

DOI10.1016/J.JDA.2018.11.013zbMath1410.68181OpenAlexW2900649734MaRDI QIDQ5915913

Narayan Vikas

Publication date: 18 January 2019

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2018.11.013

zbMATH Keywords

partitionalgorithmscomputational complexitygraphretractioncolouringhomomorphismcompactionvertex-compaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• Computational complexity of compaction to irreflexive cycles
• Absolute reflexive retracts and absolute bipartite retracts
• A characterization of absolute retracts of n-chromatic graphs
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Consistency in networks of relations
• Absolute retracts of bipartite graphs
• Networks of constraints: Fundamental properties and applications to picture processing
• List homomorphisms and circular arc graphs
• Graph partitions with prescribed patterns
• 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
• Absolute Retracts and Varieties of Reflexive Graphs
• Algorithms for Partition of Some Class of Graphs under Compaction
• Fixed-edge theorem for graphs with loops
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• List Partitions
• Compaction, Retraction, and Constraint Satisfaction
• Computing and Combinatorics
• Computational Complexity of Compaction to Reflexive Cycles
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• Monotone monadic SNP and constraint satisfaction
• Products of absolute retracts
• Computational complexity relationship between compaction, vertex-compaction, and retraction

This page was built for publication: Computational complexity relationship between compaction, vertex-compaction, and retraction