Name
Abstract | ||
|---|---|---|
We present one more proof of the fact that the class of proper interval graphs is precisely the class of unit interval graphs. The proof leads to a new and efficient O(n) time and space algorithm that transforms a proper interval model of the graph into a unit model, where all the extremes are integers in the range 0 to O(n2), solving a problem posed by Gardi (Discrete Math., 307 (22), 2906–2908, 2007). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.endm.2009.11.041 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
algorithms and data structures,graph theory,efficient representation,proper interval graphs,unit interval graphs | Discrete mathematics,Combinatorics,Indifference graph,Modular decomposition,Interval graph,Chordal graph,Treewidth,Pathwidth,Trapezoid graph,Mathematics,Maximal independent set | Journal |
Volume | ISSN | Citations |
35 | 1571-0653 | 5 |
PageRank | References | Authors |
0.55 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chih Lin | 1 | 259 | 21.22 |
| Francisco J. Soulignac | 2 | 101 | 10.56 |
| Jayme L. Szwarcfiter | 3 | 546 | 45.97 |