Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that two circuits are, say, isomorphic, if they differ only up to a permutation of the bit lines. Notice that there are clearly $n!$ ways to arrange $n$ bit lines.

share|improve this question
1  
You need to provide more context. Is this supposed to resemble one side of a printed circuit board? Most circuit layouts use more than one layer. –  The Masked Avenger Feb 4 at 19:01
2  
Are the gates rectangles arrayed in the plane? If so, perhaps your problem is reducible to computing the crossing number of a graph, which (as you likely know) is NP-hard, even for cubic graphs. –  Joseph O'Rourke Feb 4 at 20:45
    
Indeed the circuit is a graph drawn on the plane with horizontal and vertical edges: the horizontal edges are segments of the bit lines; the vertical edges are the gates. To minimize the length we can only permute the bit lines. Surely the parameter of the question is the crossing number of this graph. However, I am not sure whether it is easy to compute it given the special structure. –  Simone Severini Feb 5 at 12:32
    
Thanks for the picture. I had a completely different idea of gate. I think of sorting networks when I see your picture. Perhaps that literature might have an answer for you. My guess is that it is as hard as graph isomorphism. –  The Masked Avenger Feb 5 at 17:13
    
Try this idea: see if you can reduce Independent Set to this problem. –  The Masked Avenger Feb 5 at 17:16

1 Answer 1

up vote 11 down vote accepted
+100

If I understand your question correctly, you're trying to find a permutation of the bit lines so the maximum gate "length" is as small as possible. This is called the bandwidth problem:

Given a graph $G = (V,E)$ find a permutation $\pi : V \rightarrow [1 \ldots n]$ such that $$\max_{(i,j) \in E} |\pi(i) - \pi(j)|$$ is minimized.

The wikipedia article has more information on the complexity (it's NP-hard and APX-hard) and algorithms. The bandwidth problem is interesting also because it was used to introduce the idea of volume-respecting embeddings.

share|improve this answer
    
Then this is the answer! Thank you! –  Simone Severini Feb 12 at 1:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.