Name
Abstract | ||
|---|---|---|
Cheegeru0027s inequality states that a tightly connected subset can be extracted from a graph $G$ using an eigenvector of the normalized Laplacian associated with $G$. More specifically, we can compute a subset with conductance $O(sqrt{phi_G})$, where $phi_G$ is the minimum conductance of a set in $G$. It has recently been shown that Cheegeru0027s inequality can be extended to hypergraphs. However, as the normalized Laplacian of a hypergraph is no longer a matrix, we can only approximate to its eigenvectors; this causes a loss in the conductance of the obtained subset. To address this problem, we here consider the heat equation on hypergraphs, which is a differential equation exploiting the normalized Laplacian. We show that the heat equation has a unique solution and that we can extract a subset with conductance $sqrt{phi_G}$ from the solution. An analogous result also holds for directed graphs. |
Year | Venue | Field |
|---|---|---|
2018 | arXiv: Data Structures and Algorithms | Discrete mathematics,Differential equation,Combinatorics,Constraint graph,Hypergraph,Directed graph,Heat equation,Conductance,Eigenvalues and eigenvectors,Mathematics,Laplace operator |
DocType | Volume | Citations |
Journal | abs/1809.04396 | 0 |
PageRank | References | Authors |
0.34 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masahiro Ikeda | 1 | 2 | 3.75 |
| Atsushi Miyauchi | 2 | 26 | 7.64 |
| Yuuki Takai | 3 | 2 | 0.72 |
| Yuichi Yoshida | 4 | 81 | 11.63 |