An O(n^3) time algorithm for recognizing threshold dimension 2 graphs

DOI10.1016/S0020-0190(98)00112-4MaRDI QIDQ293369zbMATHOpenAlexFDO

Authors Andrea Sterbini, Thomas Raschle

Publication date 9 June 2016

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

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001124?np=y

zbMATH Keywords

graph algorithmsmaximum cliquesthreshold dimension 2 graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• scientific article; zbMATH DE number 1263242
• Recognizing strict 2-threshold graphs in O(m) time
• On recognition of threshold tolerance graphs and their complements
• Recognizing threshold tolerance graphs in \(O(n^2)\) time
• A finite characterization and recognition of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 in the class of threshold graphs

Cites work

• scientific article; zbMATH DE number 432839 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 1263242 (Why is no real title available?)
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Multidimensional scaling and threshold graphs
• The Complexity of the Partial Order Dimension Problem
• Threshold Dimension of Graphs
• Threshold graphs and related topics

Cited in

(5)

• The lexicographic method for the threshold cover problem
• Linear-time recognition of double-threshold graphs
• Ond-threshold graphs andd-dimensional bin packing
• A graph theoretic approach to solve special knapsack problems in polynomial time
• An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs

This page was built for publication: An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs

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