A Note on Two Problems of Nano-PLA Design

摘要

This paper shows that the subgraph isomorphism problem is NP-hard even for bipartite permutation graphs, while the balanced complete bipartite subgraph problem can be solved in O(n + m) time for a bipartite permutation graph with n vertices and m edges.