Linear-Time Recognition of Double-Threshold Graphs

A graph G = ( V , E ) is a double-threshold graph if there exist a vertex-weight function w : V → R and two real numbers lb , ub ∈ R such that u v ∈ E if and only if lb ≤ w ( u ) + w ( v ) ≤ ub . In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2022-04, Vol.84 (4), p.1163-1181
Main Authors: Kobayashi, Yusuke, Okamoto, Yoshio, Otachi, Yota, Uno, Yushi
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Apexes
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Graph theory
Graphs
Mathematics of Computing
Permutations
Real numbers
Theory of Computation
Trees (mathematics)
Weighting functions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph G = ( V , E ) is a double-threshold graph if there exist a vertex-weight function w : V → R and two real numbers lb , ub ∈ R such that u v ∈ E if and only if lb ≤ w ( u ) + w ( v ) ≤ 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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-021-00921-9