Paper Info
Title
A Note on Edge-based Graph Partitioning and its Linear Algebraic Structure
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.
Year
DOI
Venue
2011
10.1007/s10852-011-9154-4
J. Math. Model. Algorithms
Keywords
Field
DocType
linear algebraic manipulation,novel methodology,edge-based graph partitioning,linear algebra · edge-centric representation · graph partitioning · computational complexity,linear-time algorithm,essential problem,linear algebra,graph problem,np-hard problem,linear algebra theory,actual graph problem,linear algebraic structure,graph partitioning,computational complexity
Graph algebra,Discrete mathematics,Mathematical optimization,Line graph,Graph property,Edge contraction,Directed graph,Null graph,Algebraic graph theory,Voltage graph,Mathematics
Journal
Volume
Issue
ISSN
10
3
1572-9214
Citations 
PageRank 
References 
2
0.36
18
Authors
3
Name
Order
Citations
PageRank
Yourim Yoon118517.18
Yong-Hyuk Kim235540.27
Byung-Ro Moon384458.71