Computational complexity of compaction to irreflexive cycles

DOI10.1016/S0022-0000(03)00034-5MaRDI QIDQ596309zbMATH OpenFDO

Authors Narayan Vikas

Publication date 10 August 2004

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Recommendations

• Computational Complexity of Compaction to Reflexive Cycles
• scientific article; zbMATH DE number 1305547
• On the complexity of orthogonal compaction
• scientific article; zbMATH DE number 2185601
• scientific article; zbMATH DE number 769607
• scientific article; zbMATH DE number 2188410
• Computational complexity of fixed points and intersection points
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• Computational complexity of fixed points
• The complexity of some complementation problems

Cites work

• scientific article; zbMATH DE number 3758365 (Why is no real title available?)
• scientific article; zbMATH DE number 40997 (Why is no real title available?)
• scientific article; zbMATH DE number 3463659 (Why is no real title available?)
• scientific article; zbMATH DE number 1305547 (Why is no real title available?)
• A characterization of absolute retracts of n-chromatic graphs
• Absolute Retracts and Varieties of Reflexive Graphs
• Absolute reflexive retracts and absolute bipartite retracts
• Absolute retracts of bipartite graphs
• Computational Complexity of Compaction to Reflexive Cycles
• Fixed-edge theorem for graphs with loops
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• On the complexity of H-coloring
• Parallel concepts in graph theory

Cited in

(13)

• scientific article; zbMATH DE number 2185601 (Why is no real title available?)
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Computational complexity relationship between compaction, vertex-compaction, and retraction
• Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
• The complexity of surjective homomorphism problems-a survey
• Mixing 3-colourings in bipartite graphs
• Surjective \texttt{H}-colouring over reflexive digraphs
• Mixing 3-Colourings in Bipartite Graphs
• Computational Complexity of Compaction to Reflexive Cycles
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• The complexity of counting surjective homomorphisms and compactions
• Algorithms for partition of some class of graphs under compaction
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon

This page was built for publication: Computational complexity of compaction to irreflexive cycles

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