| Article ID: | iaor20118620 |
| Volume: | 10 |
| Issue: | 3 |
| Start Page Number: | 269 |
| End Page Number: | 276 |
| Publication Date: | Sep 2011 |
| Journal: | Journal of Mathematical Modelling and Algorithms |
| Authors: | Moon Byung-Ro, Yoon Yourim, Kim Yong-Hyuk |
| Keywords: | graph partitioning, linear algebra, polynomial programs |
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.