zbMATH — the first resource for mathematics

Nonconstructive advances in polynomial-time complexity. (English) Zbl 0637.68053
The following decision problem is defined: Gate matrix layout (GML): Instance: A Boolean matrix M and an integer k; Question: Can we permute the columns of M such that if in each row we change to * every 0 lying between the row’s leftmost and rightmost 1, then no column contains more than k 1’s and *’s ?
The main result of the paper is that the fixed-k version of GML is solvable in polynomial time. The proof is nonconstructive and is based on a result of N. Robertson and P. D. Seymour [SIAM J. Algebraic Discrete Methods 6, 300-305 (1985; Zbl 0565.05045)].
Reviewer: C.Radu

68Q25 Analysis of algorithms and problem complexity
68R99 Discrete mathematics in relation to computer science
Full Text: DOI
[1] Deo, N.; Krishnamoorthy, M.; Langston, M., Exact and approximate solutions for the gate matrix layout problem, IEEE trans. computer aided design, 6, 79-84, (1987)
[2] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[3] Horowitz, E.; Sahni, S., Fundamentals of computer algorithms, (1984), Computer Science Press Potomac, MD
[4] D. Hwang, W. Fuchs and S. Kang, An efficient approach to gate matrix layout, IEEE Internat. Conf. on Computer-Aided Design, to appear.
[5] D. Hwang and H. Leong, Private communication, 1986.
[6] Kashiwabara, T.; Fujisawa, T., An NP-complete problem on interval graphs, (), 82-83
[7] H. Leong, A new algorithm for gate matrix layout, IEEE Internat. Conf. on Computer-Aided Design, to appear.
[8] Li, J., Algorithms for gate matrix layout, (), 1013-1016
[9] Lopez, A.; Law, H., A dense gate matrix layout method for MOS VLSI, IEEE trans. electron. devices, 27, 1671-1675, (1980)
[10] Robertson, N.; Seymour, P., Disjoint paths — A survey, SIAM J. alg. disc. meths., 6, 300-305, (1985) · Zbl 0565.05045
[11] Robertson, N.; Seymour, P., Graph minors — A survey, (), 153-171
[12] Rubin, H.; Rubin, J., Equivalents of the axiom of choice, (1985), North-Holland Amsterdam · Zbl 0582.03033
[13] P. Seymour, Private communication, 1986.
[14] Wagner, K., Uber einer eigenschaft der ebener complexe, Math. ann., 14, 570-590, (1937) · Zbl 0017.19005
[15] Wing, O.; Huang, S.; Wang, R., Gate matrix layout, IEEE trans. computer-aided design, 4, 220-231, (1985)
[16] Fellows, M.R.; Langston, M.A., Nonconstructive tools for proving polynomial-time decidability, () · Zbl 0652.68049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.