Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time

DOI10.1007/978-3-319-12340-0_18zbMath1417.05208OpenAlexW2174180199MaRDI QIDQ2945191

Petr A. Golovach, Nathan Lindzey, Pinar Heggernes, Jeremy P. Spinrad, Vinícius Fernandes dos Santos, Ross M. McConnell

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tolerance graphs
• Characterizations of strongly chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient graph representations
• Linear-time recognition of circular-arc graphs
• Doubly lexical ordering of dense 0--1 matrices
• Co-TT graphs and a characterization of split co-TT graphs
• Threshold tolerance graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Graph Classes: A Survey

This page was built for publication: Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time