Loose Cover of Graphs |
| |
Authors: | Satoshi Fujita |
| |
Institution: | 1.Department of Information Engineering, Graduate School of Engineering,Hiroshima University,Higashi-Hiroshima,Japan |
| |
Abstract: | This paper introduces a new definition of embedding a local structure to a given network, called loose cover of graphs. We derive several basic properties on the notion of loose cover, which includes transitivity, maximality, and
the computational complexity of finding a loose cover by paths and cycles. In particular, we show that the decision problem
is in P if the given local structure is a path with three or less vertices, while it is NP-complete for paths consisting of
six or more vertices. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|