On recognition of threshold tolerance graphs and their complements

详细信息    查看全文

• 作者：Petr A. Golovach^a ; ^{Petr.Golovach@ii.uib.no} ; Pinar Heggernes^a ; ^{pinar@ii.uib.no} ; Nathan Lindzey^b ; ^{lindzey@cs.colostate.edu} ; Ross M. McConnell^c ; ^{rmm@cs.colostate.edu} ; Viní ; cius Fernandes dos Santos^d ; ^{vinicius@ime.uerj.br} ; Jeremy P. Spinrad^e ; ^{spin@vuse.vanderbilt.edu} ; Jayme Luiz Szwarcfiter^f ; ^{jayme@nce.ufrj.br}
• 关键词：Graph classes ; Recognition algorithms ; Threshold-tolerance graphs ; Strongly chordal graphs ; Interval graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：171-180
• 全文大小：502 K
• 卷排序：216

文摘

A graph G=(V,E)G=(V,E) is a threshold tolerance   graph if each vertex v∈Vv∈V can be assigned a weight wvwv and a tolerance tvtv such that two vertices x,y∈Vx,y∈V are adjacent if wx+wy≥min(tx,ty)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)O(n4) runtime. We give an O(n2)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.