Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations

1. Bai, G.: Ein eingeschränktes Knotenüberdeckungsproblem in bipartiten Graphen. Diplomarbeit, FB IV, Informatik, Universität Trier, Germany (2007)

   Google Scholar 

2. Blough, D.M.: On the reconfiguration of memory arrays containing clustered faults. In: Fault Tolerant Computing, pp. 444–451. IEEE Press, Los Alamitos (1991)

   Google Scholar 

3. Blough, D.M., Pelc, A.: A clustered failure model for the memory array reconfiguration problem. IEEE Transactions on Computers 42(5), 518–528 (1993)

   Article  Google Scholar 

4. Chen, J., Kanj, I.A.: Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithmics. Journal of Computer and System Sciences 67, 833–847 (2003)

   Article  MATH  MathSciNet  Google Scholar 

5. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)

   Google Scholar 

6. Evans, R.C.: Testing repairable RAMs and mostly good memories. In: Proceedings of the IEEE Int’l Test Conf., pp. 49–55 (1981)

   Google Scholar 

7. Fernau, H.: On parameterized enumeration. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2383, pp. 564–573. Springer, Heidelberg (2002)

   Chapter  Google Scholar 

8. Fernau, H.: Parameterized Algorithmics: A Graph-Theoretic Approach, Habilitationsschrift, Universität Tübingen, Germany (2005)

   Google Scholar 

9. Fernau, H., Niedermeier, R.: An efficient exact algorithm for constraint bipartite vertex cover. Journal of Algorithms 38(2), 374–410 (2001)

   Article  MATH  MathSciNet  Google Scholar 

10. Haddad, R.W., Dahbura, A.T., Sharma, A.B.: Increased throughput for the testing and repair of RAMs with redundancy. IEEE Transactions on Computers 40(2), 154–166 (1991)

    Article  MathSciNet  Google Scholar 

11. Handa, K., Haruki, K.: A reconfiguration algorithm for memory arrays containing faulty spares. IEICE Trans. Fundamentals E83-A(6), 1123–1130 (2000)

    Google Scholar 

12. Koren, I., Pradhan, D.K.: Modeling the effect of redundancy on yield and performance of VLSI systems. IEEE Transactions on Computers 36(3), 344–355 (1987)

    Article  Google Scholar 

13. Kuo, S.-Y., Fuchs, W.K.: Efficient spare allocation for reconfigurable arrays. IEEE Design and Test 4, 24–31 (1987)

    Article  Google Scholar 

14. Lin, H.-Y., Yeh, F.-M., Kuo, S.-Y.: An efficient algorithm for spare allocation problems. IEEE Transactions on Reliability 55(2), 369–378 (2006)

    Article  Google Scholar 

15. Lombardi, F., Huang, W.K.: Approaches to the repair of VLSI/WSI PRAMs by row/column deletion. In: International Symposium on Fault-Tolerant Computing (FTCS 1988), pp. 342–347. IEEE Press, Los Alamitos (1988)

    Chapter  Google Scholar 

16. Meyer, F.J., Pradhan, D.K.: Modeling defect spatial distribution. IEEE Transactions on Computers 38(4), 538–546 (1989)

    Article  Google Scholar 

17. Shi, W., Fuchs, W.K.: Probabilistic analysis and algorithms for reconfiguration of memory arrays. IEEE Transactions on Computer-Aided Design 11(9), 1153–1160 (1992)

    Article  Google Scholar 

18. Wang, J., Xu, X., Liu, Y.: An Exact Algorithm Based on Chain Implication for the Min-CVCB Problem. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) COCOA. LNCS, vol. 4616, pp. 343–353. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

Download references