Linear-Time Recognition of Double-Threshold Graphs
| Autor: | Yoshio Okamoto, Yushi Uno, Yota Otachi, Yusuke Kobayashi |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Physics
Double threshold Bipartite permutation graphs 0102 computer and information sciences 02 engineering and technology Function (mathematics) Characterization (mathematics) 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Recognition algorithm Time complexity Real number |
| Zdroj: | Graph-Theoretic Concepts in Computer Science ISBN: 9783030604394 WG |
| Popis: | 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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|