1 - 10 of 10 articles
For a graph G(V, E) (V = n) and a vertex s V, a weighting scheme (W : E Z+) is called a min-unique (resp. max-unique) weighting scheme if, for any vertex v of the graph G, there is a unique path of minimum (resp. maximum) weight from s to v, where weight of a path is the sum of the weights...
Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A...
A sampling procedure for a distribution P over 0, 1 is a function C 0, 1n 0, 1 such that the distribution C(Un) (obtained by applying C on the uniform distribution Un) is the desired distribution P. Let n > r = n(1). An -nb-PRG (defined by Dubrov and Ishai ) is a function G 0, 1r 0, 1n...
We examine the computational complexity of approximately counting the list H-colorings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph, then counting list H-colorings is...
A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and bipartite complete graphs, the exact perfect matching problem...
Read and print from thousands of top scholarly journals.
Continue with Facebook
Log in with Microsoft
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Sign Up Log In
To subscribe to email alerts, please log in first, or sign up for a DeepDyve account if you don’t already have one.
To get new article updates from a journal on your personalized homepage, please log in first, or sign up for a DeepDyve account if you don’t already have one.