Recognizing threshold tolerance graphs in O(n^2) time

DOI10.1007/978-3-319-12340-0_18MaRDI QIDQ2945191zbMATH OpenOpenAlexFDO

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

Publication date 9 September 2015

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-12340-0_18

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On recognition of threshold tolerance graphs and their complements
• Threshold tolerance graphs
• Co-TT graphs and a characterization of split co-TT graphs
• Recognizing Bipartite Tolerance Graphs in Linear Time
• scientific article; zbMATH DE number 4053682

Cites work

• 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
• Graph Classes: A Survey
• 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 2090048 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• 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
• Threshold tolerance graphs
• Tolerance graphs

Cited in

(7)

• Co-TT graphs and a characterization of split co-TT graphs
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• On recognition of threshold tolerance graphs and their complements
• Threshold tolerance graphs
• Linear-time recognition of double-threshold graphs
• Linear-time recognition of double-threshold graphs
• Recognizing strict 2-threshold graphs in O(m) time

This page was built for publication: Recognizing threshold tolerance graphs in \(O(n^2)\) time

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