Recognizing strict 2-threshold graphs in O(m) time

DOI10.1016/0020-0190(95)00030-GzbMath0875.68453OpenAlexW2022597688MaRDI QIDQ673666

Andrea Sterbini, Rossella Petreschi

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00030-g

zbMATH Keywords

AlgorithmsRecognition algorithmsThreshold graphsThreshold number

Mathematics Subject Classification ID

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

Related Items (1)

An \(O(n^ 3)\) recognition algorithm for bithreshold graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Strict 2-threshold graphs
• On the notion of balance of a signed graph
• The Complexity of the Partial Order Dimension Problem
• Some properties of 2-threshold graphs
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives

This page was built for publication: Recognizing strict 2-threshold graphs in O(m) time