Name
Abstract | ||
|---|---|---|
A graph $G = (V,E)$ is a double-threshold graph if there exist a vertex-weight function $w \colon V \to \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 as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs, which gives connections 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 [COCOON 2018] ran in $O(n^6)$ time, where $n$ is the number of vertices. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-60440-0_23 | WG |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kobayashi Yusuke | 1 | 0 | 0.34 |
| Yoshio Okamoto | 2 | 170 | 28.50 |
| Yota Otachi | 3 | 161 | 37.16 |
| yushi uno | 4 | 222 | 28.80 |