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

Autor:	Nathan Lindzey, Vinícius Fernandes dos Santos, Jeremy P. Spinrad, Pinar Heggernes, Ross M. McConnell, Petr A. Golovach
Rok vydání:	2014
Předmět:	Combinatorics Interval model Chordal graph Interval graph Split graph Recognition algorithm Algorithm Graph Vertex (geometry) Mathematics
Zdroj:	Graph-Theoretic Concepts in Computer Science ISBN: 9783319123394 WG
DOI:	10.1007/978-3-319-12340-0_18
Popis:	A graph \(G = (V,E)\) is a threshold tolerance graph if each vertex \(v \in V\) can be assigned a weight \(w_v\) and a tolerance \(t_v\) such that two vertices \(x,y \in V\) are adjacent if \(w_x + w_y \ge \min (t_x,t_y)\). Currently, the most efficient recognition algorithm for threshold tolerance graphs is the algorithm of Monma, Reed, and Trotter which has an \(O(n^4)\) runtime. We give an \(O(n^2)\) algorithm for recognizing threshold tolerance and their complements, the co-threshold tolerance (co-TT) graphs, resolving an open question of Golumbic, Weingarten, and Limouzy.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8dcc2efad0feada37c62dd1f395a3937 https://doi.org/10.1007/978-3-319-12340-0_18 Zobrazit plný text záznamu