Linear-time recognition of double-threshold graphs

DOI10.1007/s00453-021-00921-9OpenAlexW4205499603MaRDI QIDQ5970798

Yushi Uno, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00921-9

zbMATH Keywords

bipartite permutation graphdouble-threshold graphstar pairwise compatibility graph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items

Combinatorics, graph theory, and computing ⋮ On star-multi-interval pairwise compatibility graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Bipartite permutation graphs
• Modular decomposition and transitive orientation
• Short proofs for interval digraphs
• Mock threshold graphs
• Paired threshold graphs
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• Quasi-threshold graphs
• Double-threshold permutation graphs
• Some results on multithreshold graphs
• Pairwise Compatibility Graphs: A Survey
• Bithreshold Graphs
• Threshold characterization of graphs with dilworth number two
• Threshold tolerance graphs
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Weakly threshold graphs
• Interval bigraphs and circular arc graphs
• Multithreshold graphs
• Transitiv orientierbare Graphen
• Characterizing star-PCGs