Linear-time recognition of double-threshold graphs

DOI10.1007/978-3-030-60440-0_23MaRDI QIDQ5918597zbMATH OpenOpenAlexFDO

Authors Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

Publication date 21 December 2022

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.09371

zbMATH Keywords

bipartite permutation graphdouble-threshold graphrecognition algorithmstar pairwise compatibility graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Linear-time recognition of double-threshold graphs
• Double-threshold permutation graphs
• Recognizing threshold tolerance graphs in O(n^2) time
• On recognition of threshold tolerance graphs and their complements
• Recognizing strict 2-threshold graphs in O(m) time

Cited in

(3)

• Double-threshold permutation graphs
• Linear-time recognition of double-threshold graphs
• Linear-Time Recognition of Double-Threshold Graphs

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 Q5918597)