58 citations · 151 across the 35 of their papers we have counts for
3 papers · 1 filter
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
We say that an instance of a constraint satisfaction problem (CSP) is non-redundant if the satisfaction of each clause cannot be implied by the satisfaction of the other clauses in…
The Richness of CSP Non-redundancy
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of CSP is call…
Acyclicity in Edge-Colored Graphs
Gregory Gutin, Mark Jones, Bin Sheng +2
A walk in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in is of different color. We introduce and study five types of PC acyclicit…