Linear-time recognition of double-threshold graphs

DOI10.1007/S00453-021-00921-9MaRDI QIDQ5970798zbMATH OpenOpenAlexFDO

Authors Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

Publication date 22 March 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• Linear-time recognition of double-threshold graphs
• Characterization and linear-time recognition of paired threshold graphs
• Recognizing strict 2-threshold graphs in O(m) time
• A simple linear-time recognition algorithm for weakly quasi-threshold graphs
• scientific article; zbMATH DE number 1263242
• Recognizing threshold tolerance graphs in O(n^2) time
• Linear-time recognition of bipartite graphs plus two edges
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• Fast recognition of doubled graphs
• Linear time recognition algorithms and structure theorems for bipartite tolerance graphs and bipartite probe interval graphs

Cites work

• scientific article; zbMATH DE number 1263242 (Why is no real title available?)
• scientific article; zbMATH DE number 1156661 (Why is no real title available?)
• scientific article; zbMATH DE number 7378386 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• Bipartite permutation graphs
• Bithreshold Graphs
• Double-threshold permutation graphs
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Interval bigraphs and circular arc graphs
• Mock threshold graphs
• Modular decomposition and transitive orientation
• Multithreshold graphs
• Paired threshold graphs
• Pairwise compatibility graphs: a survey
• Quasi-threshold graphs
• Short proofs for interval digraphs
• Some results on multithreshold graphs
• Threshold characterization of graphs with dilworth number two
• Threshold graphs and related topics
• Threshold tolerance graphs
• Transitiv orientierbare Graphen
• Weakly threshold graphs

Cited in

(3)

• On star-k-PCGs: exploring class boundaries for small k values
• Combinatorics, graph theory, and computing
• On star-multi-interval pairwise compatibility graphs

This page was built for publication: Linear-time recognition of double-threshold graphs

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