Name
Abstract | ||
|---|---|---|
A graph
$$G = (V,E)$$
is a double-threshold graph if there exist a vertex-weight function
$$w :V \rightarrow \mathbb {R}$$
and two real numbers
$$\mathtt {lb}, \mathtt {ub}\in \mathbb {R}$$
such that
$$uv \in E$$
if and only if
$$\mathtt {lb}\le \mathtt {w}(u) + \mathtt {w}(v) \le \mathtt {ub}$$
. In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in
$$O(n^{3} m)$$
time, where n and m are the numbers of vertices and edges, respectively. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s00453-021-00921-9 | Algorithmica |
Keywords | DocType | Volume |
Double-threshold graph, Bipartite permutation graph, Star pairwise compatibility graph | Journal | 84 |
Issue | ISSN | Citations |
4 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kobayashi, Yusuke | 1 | 0 | 0.34 |
| Yoshio Okamoto | 2 | 15 | 2.71 |
| Yota Otachi | 3 | 161 | 37.16 |
| Uno, Yushi | 4 | 0 | 0.34 |