On recognition of threshold tolerance graphs and their complements

DOI10.1016/j.dam.2015.01.034zbMath1350.05054OpenAlexW2000263143MaRDI QIDQ344853

Petr A. Golovach, Ross M. McConnell, Nathan Lindzey, Pinar Heggernes, Jeremy P. Spinrad, Vinícius Fernandes dos Santos, Jayme Luiz 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

recognition algorithmsinterval graphsgraph classesstrongly chordal graphsthreshold-tolerance graphs

Mathematics Subject Classification ID

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

Related Items (6)

Query-competitive sorting with uncertainty ⋮ Recognition of linear and star variants of leaf powers is in P ⋮ Unnamed Item ⋮ Min-Orderable Digraphs ⋮ Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Three Partition Refinement Algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• Perfect Elimination and Chordal Bipartite Graphs

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