Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949892 | Discrete Applied Mathematics | 2017 | 10 Pages |
Abstract
A graph G=(V,E) is a threshold tolerance graph if each vertex vâV can be assigned a weight wv and a tolerance tv such that two vertices x,yâV are adjacent if wx+wyâ¥min(tx,ty). Currently, the most efficient recognition algorithm for threshold tolerance graphs is the algorithm of Monma, Reed, and Trotter which has an O(n4) runtime. We give an O(n2) algorithm for recognizing threshold tolerance and their complements, the co-threshold tolerance (co-TT) graphs, resolving an open question of Golumbic, Weingarten, and Limouzy.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Petr A. Golovach, Pinar Heggernes, Nathan Lindzey, Ross M. McConnell, VinÃcius Fernandes dos Santos, Jeremy P. Spinrad, Jayme Luiz Szwarcfiter,