A Note on Edge-based Graph Partitioning and its Linear Algebraic Structure |
| |
| Authors: | Yourim Yoon Yong-Hyuk Kim Byung-Ro Moon |
| |
| Institution: | 1. School of Computer Science & Engineering, Seoul National University, 599 Gwanak-ro, Gwanak-gu, Seoul, 151-744, Korea
2. Department of Computer Science & Engineering, Kwangwoon University, 20 Kwangwoon-ro, Nowon-gu, Seoul, 139-701, Korea
|
| |
| Abstract: | We analyze two essential problems arising from edge-based graph partitioning. We show that one of them is an NP-hard problem
but the other is in P, presenting a novel methodology that links linear algebra theory to the graph problems as a part of
proving the facts. This is a significant trial in that linear algebra, which has been mostly adopted as a theoretical analysis
tool, is practically applied to solving actual graph problems. As a result of the linear algebraic manipulation, we could
devise a linear-time algorithm for the problem in P. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
