On recognition of threshold tolerance graphs and their complements

DOI10.1016/J.DAM.2015.01.034MaRDI QIDQ344853zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Pinar Heggernes, Nathan Lindzey, R. M. McConnell, Jeremy P. Spinrad, Vinícius F. dos Santos, Jayme L. Szwarcfiter

Publication date 24 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.01.034

zbMATH Keywords

interval graphsgraph classesrecognition algorithmsstrongly chordal graphsthreshold-tolerance graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Recommendations

• Recognizing threshold tolerance graphs in O(n^2) time
• Threshold tolerance graphs
• Co-TT graphs and a characterization of split co-TT graphs
• scientific article; zbMATH DE number 4053682
• Recognizing Bipartite Tolerance Graphs in Linear Time

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Graphs
• Characterizations of strongly chordal graphs
• Co-TT graphs and a characterization of split co-TT graphs
• Doubly lexical ordering of dense 0--1 matrices
• Efficient graph representations
• Linear-time recognition of circular-arc graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Three Partition Refinement Algorithms
• Threshold tolerance graphs

Cited in

(11)

• scientific article; zbMATH DE number 4053682 (Why is no real title available?)
• Co-TT graphs and a characterization of split co-TT graphs
• Recognizing threshold tolerance graphs in O(n^2) time
• Recognition of linear and star variants of leaf powers is in P
• Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• Min-orderable digraphs
• Threshold tolerance graphs
• Query-competitive sorting with uncertainty
• Interval-like graphs and digraphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

This page was built for publication: On recognition of threshold tolerance graphs and their complements

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