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

DOI10.1016/0020-0190(95)00030-GMaRDI QIDQ673666zbMATH OpenOpenAlexFDO

Authors Rossella Petreschi, Andrea Sterbini

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)

Recommendations

• Strict 2-threshold graphs
• Some properties of 2-threshold graphs
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• Recognizing threshold tolerance graphs in O(n^2) time
• An \(O(n^ 3)\) recognition algorithm for bithreshold graphs

Cites work

• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• scientific article; zbMATH DE number 3561379 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• On the notion of balance of a signed graph
• Some properties of 2-threshold graphs
• Strict 2-threshold graphs
• The Complexity of the Partial Order Dimension Problem

Cited in

(6)

• Strict 2-threshold graphs
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• Some properties of 2-threshold graphs
• Linear-time recognition of double-threshold graphs
• Linear-time recognition of double-threshold graphs
• An \(O(n^ 3)\) recognition algorithm for bithreshold graphs

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

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