Name
Abstract | ||
|---|---|---|
We consider the constrained graph alignment problem which has applications in biological network analysis studies. Given two input graphs $G_1, G_2$, a pair of vertex mappings induces an edge conservation if the vertex pairs are adjacent in their respective graphs. In general terms the goal is to provide a one-to-one mapping between the vertices of the input graphs such that edge conservation is maximized. However the allowed mappings are restricted. Let $m_1$ ($m_2$) denote the number of $G_2$-vertices ($G_1$-vertices) that each $G_1$-vertex ($G_2$-vertex) is allowed to be mapped to. All provided results assume $m_2=1$, except for the fixed-parameter tractability result for bounded degree graphs which applies to the more general setting of any constant $m_1, m_2$. We present a polynomial time solution for the special case where $G_1$ is acyclic. Relaxing the constraint on $G_1$, for the setting of $m_1=2$, we provide several structural properties that lead to polynomial-time approximation algorithms. We then relax the constraint on $m_1$ and consider any positive integer constant $m_1$. We provide further structural properties for this setting which lead to several additional approximation algorithms with approximation ratios better than those of the previous studies. For the same setting, we also show that the problem is fixed-parameter tractable, parameterized only by the output size. Previously the same result was known only for bounded degree graphs. We finally consider the more general setting where $m_1, m_2$ can be any positive integer constant and provide an approximation algorithm and a fixed-parameter tractability result that applies to bounded degree graphs. |
Year | Venue | Field |
|---|---|---|
2014 | arXiv: Data Structures and Algorithms | Integer,Approximation algorithm,Discrete mathematics,Combinatorics,Parameterized complexity,Vertex (geometry),Biological network,Time complexity,Mathematics,Bounded function,Special case |
DocType | Volume | Citations |
Journal | abs/1403.7948 | 0 |
PageRank | References | Authors |
0.34 | 8 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ferhat Alkan | 1 | 44 | 3.17 |
| Türker Bíyíkoglu | 2 | 88 | 7.40 |
| Marc Demange | 3 | 267 | 29.78 |
| Cesim Erten | 4 | 249 | 16.76 |