Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
DOI10.4230/LIPICS.MFCS.2017.69zbMATH Open1441.68197OpenAlexW2773731510MaRDI QIDQ5111286FDOQ5111286
Publication date: 26 May 2020
Full work available at URL: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2017.html#Vikas17
Recommendations
- Computational complexity of compaction to irreflexive cycles
- Computational Complexity of Compaction to Reflexive Cycles
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- Algorithms for partition of some class of graphs under compaction
- Computing and Combinatorics
graph partitioncomputational complexitycolouringgraph algorithmshomomorphismretractioncompactionvertex-compaction
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- On the complexity of H-coloring
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Title not available (Why is that?)
- Monotone monadic SNP and constraint satisfaction
- Complexity of graph partition problems
- List Partitions
- Graph partitions with prescribed patterns
- List homomorphisms and circular arc graphs
- Absolute reflexive retracts and absolute bipartite retracts
- List homomorphisms to reflexive graphs
- Fixed-edge theorem for graphs with loops
- 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
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- Title not available (Why is that?)
- Compaction, Retraction, and Constraint Satisfaction
- Computing and Combinatorics
- Computational Complexity of Compaction to Reflexive Cycles
- Computational complexity of compaction to irreflexive cycles
- Absolute retracts of bipartite graphs
- Absolute Retracts and Varieties of Reflexive Graphs
- Title not available (Why is that?)
- A characterization of absolute retracts of n-chromatic graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (6)
- Coloring problems on bipartite graphs of small diameter
- Computational complexity relationship between compaction, vertex-compaction, and retraction
- Title not available (Why is that?)
- Computational Complexity of Compaction to Reflexive Cycles
- Constraint satisfaction problem: what makes the problem easy
- Computational complexity of compaction to irreflexive cycles
This page was built for publication: Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111286)
