Name
Abstract | ||
|---|---|---|
A graph G = (V,E) is a tolerance graph if each vertex v ∈ V can be associated with an interval of the real line Iv and a positive real number tv in such a way that (uv) ∈ E if and only if |Iv ∩ Iu| ≥ min(tv, tu). No algorithm for recognizing tolerance graphs in general is known. In this paper we present an O(n + m) algorithm for recognizing tolerance graphs that are also bipartite, where n and m are the number vertices and edges of the graph, respectively. We also give a new structural characterization of these graphs based on the algorithm. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74839-7_2 | WG |
Keywords | Field | DocType |
new structural characterization,positive real number tv,real line,graph g,linear time,number vertex,bipartite tolerance graph,tolerance graph,vertex v | Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Bipartite graph,Cograph,Pathwidth,1-planar graph,Mathematics,Pancyclic graph,Triangle-free graph | Conference |
Volume | ISSN | ISBN |
4769 | 0302-9743 | 3-540-74838-5 |
Citations | PageRank | References |
2 | 0.40 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arthur H. Busch | 1 | 42 | 6.61 |
| Garth Isaak | 2 | 172 | 24.01 |