A Note on Edge-based Graph Partitioning and its Linear Algebraic Structure |
| |
Authors: | Yourim Yoon Yong-Hyuk Kim Byung-Ro Moon |
| |
Affiliation: | 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 等数据库收录! |
|