Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HOMOMORPHISMS:
Reports tagged with Homomorphisms:
TR95-011 | 15th February 1995
Roman Bacik, Sanjeev Mahajan

#### Semidefinite Programming and its Applications to NP Problems

The graph homomorphism problem is a canonical $NP$-complete problem.
It generalizes various other well-studied problems such as graph
coloring and finding cliques. To get a better insight into a
combinatorial problem, one often studies relaxations of the problem.
We define fractional homomorphisms and pseudo-homomorphisms ... more >>>

TR05-085 | 5th August 2005
Asaf Shapira, Noga Alon

#### Homomorphisms in Graph Property Testing - A Survey

Property-testers are fast randomized algorithms for distinguishing
between graphs (and other combinatorial structures) satisfying a
certain property, from those that are far from satisfying it. In
many cases one can design property-testers whose running time is in
fact {\em independent} of the size of the input. In this paper we
more >>>

TR20-177 | 12th October 2020
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

#### Counting Subgraphs in Degenerate Graphs

We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has {\em bounded degeneracy}. ... more >>>

ISSN 1433-8092 | Imprint