Linear-Time Recognition of Double-Threshold Graphs
| Autor: | Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) General Computer Science Applied Mathematics Double-threshold graph Bipartite permutation graph Computer Science Applications Star pairwise compatibility graph Computer Science - Data Structures and Algorithms FOS: Mathematics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) Computer Science - Discrete Mathematics |
| Zdroj: | Algorithmica. 84:1163-1181 |
| ISSN: | 1432-0541 0178-4617 |
| Popis: | 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 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. 18 pages, 8 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink