Testing list H-homomorphisms

DOI10.1007/S00037-014-0093-0MaRDI QIDQ347111zbMATHOpenAlexFDO

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

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)

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

Cites work

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

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)