An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
From MaRDI portal
Publication:293369
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
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