An O(n^3) time algorithm for recognizing threshold dimension 2 graphs
DOI10.1016/S0020-0190(98)00112-4zbMATH Open1339.05405OpenAlexW2081573399MaRDI QIDQ293369FDOQ293369
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
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
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)
Cites Work
- Threshold graphs and related topics
- Title not available (Why is that?)
- The Complexity of the Partial Order Dimension Problem
- Multidimensional scaling and threshold graphs
- Title not available (Why is that?)
- Threshold Dimension of Graphs
- A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
- Title not available (Why is that?)
Cited In (5)
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)
