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

DOI10.1016/S0020-0190(98)00112-4zbMath1339.05405OpenAlexW2081573399MaRDI QIDQ293369

Thomas Raschle, Andrea Sterbini

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

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

Related Items

The lexicographic method for the threshold cover problem, A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time, Linear-time recognition of double-threshold graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multidimensional scaling and threshold graphs
• Threshold graphs and related topics
• Threshold Dimension of Graphs
• The Complexity of the Partial Order Dimension Problem
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives