Abstract
We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number and the minimal rectifier network size of a bipartite graph . We show that there exist graphs with . As a corollary, we establish that there exist nondeterministic finite automata (NFAs) with -transitions, having transitions total such that the smallest equivalent -free NFA has transitions. We also formulate a version of previous bounds for the weighted set cover problem and discuss its connections to giving upper bounds for the possible blow-up.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.