Linear-Time Recognition of Double-Threshold Graphs

DOI10.1007/978-3-030-60440-0_23arXiv1909.09371MaRDI QIDQ6325674FDOQ6325674

Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

Publication date: 20 September 2019

Abstract: A graph $G=(V,E)$ is a double-threshold graph if there exist a vertex-weight function $wcolonVomathbbR$ and two real numbers $mathttlb,mathttubinmathbbR$ such that $uvinE$ if and only if $mathttlblemathttw(u)+mathttw(v)lemathttub$. 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.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Signed and weighted graphs (05C22)

This page was built for publication: Linear-Time Recognition of Double-Threshold Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325674)