Bithreshold Graphs

DOI10.1137/0606049MaRDI QIDQ3701461zbMATH OpenOpenAlexFDO

Authors Peter L. Hammer, N. V. R. Mahadev

Publication date 1985

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0606049

zbMATH Keywords

decompositionrecognitionthreshold graphsbithreshold graphs

Mathematics Subject Classification ID

Graph theory (05C99)

Recommendations

• Bipartite bithreshold graphs
• Publication:4724665
• Bithreshold graphs
• An \(O(n^ 3)\) recognition algorithm for bithreshold graphs
• Investigations on the bisection problem

Cites work

• scientific article; zbMATH DE number 3889565 (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

Cited in

(21)

• Strict 2-threshold graphs
• Bithreshold graphs
• Linear-time recognition of double-threshold graphs
• Finding houses and holes in graphs
• Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates
• scientific article; zbMATH DE number 3997845 (Why is no real title available?)
• Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
• Lower bounds and algorithms for the 2-dimensional vector packing problem
• The relationship between the threshold dimension of split graphs and various dimensional parameters
• Degree sequences and majorization
• A branch-and-bound algorithm for the two-dimensional vector packing problem
• Double-threshold permutation graphs
• Probe threshold and probe trivially perfect graphs
• Thin strip graphs
• Some properties of 2-threshold graphs
• Investigations on the bisection problem
• On dimensional properties of graphs
• Bigeodetic graphs
• On randomized stopping points and perfect graphs
• An \(O(n^ 3)\) recognition algorithm for bithreshold graphs
• Bipartite bithreshold graphs

This page was built for publication: Bithreshold Graphs

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