Testing list H-homomorphisms

DOI10.1007/S00037-014-0093-0zbMATH Open1353.68139OpenAlexW2462341721MaRDI QIDQ347111FDOQ347111

Authors: Yuichi Yoshida 

Publication date: 30 November 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-014-0093-0

Recommendations

• Bi‐arc graphs and the complexity of list homomorphisms
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• scientific article; zbMATH DE number 2151253
• The complexity of the list homomorphism problem for graphs

zbMATH Keywords

constraint satisfaction problemsproperty testinguniversal algebralist \(H\)-homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Applications of universal algebra in computer science (08A70)

Cites Work

• On the complexity of H-coloring
• Property testing and its connection to learning and approximation
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Recent Results on the Algebraic Approach to the CSP
• Property testing in bounded degree graphs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Combinatorial problems raised from 2-semilattices
• Introduction to testing graph properties
• Monotonicity testing over general poset domains
• Testing st-Connectivity
• The structure of finite algebras
• Algorithmic and analysis techniques in property testing
• Title not available (Why is that?)
• Some 3CNF Properties Are Hard to Test
• Testing the \((s,t)\) connectivity of graphs and digraphs
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A sublinear bipartiteness tester for bounded degree graphs
• Title not available (Why is that?)
• \(H\)-coloring dichotomy revisited
• List homomorphisms and circular arc graphs
• The complexity of the list homomorphism problem for graphs
• List homomorphisms to reflexive graphs
• Universal algebra and applications in theoretical computer science
• On the query complexity of testing orientations for being Eulerian
• Near-Unanimity Functions and Varieties of Reflexive Graphs
• Algebraic property testing: the role of invariance
• Testing satisfiability
• Bi‐arc graphs and the complexity of list homomorphisms
• Property testing of massively parametrized problems -- a survey
• A unified framework for testing linear‐invariant properties
• An algebraic characterization of testable Boolean CSPs
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP

Cited In (1)

• The spaces of Siegel cusp forms of degree two and the representation of \(\mathrm{Sp}(2,\mathbb F_ p)\)

This page was built for publication: Testing list \(H\)-homomorphisms

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