Name
Abstract | ||
|---|---|---|
We consider vertex coloring of a simple acyclic digraph G in such a way that two vertices which have a common ancestor in G receive distinct colors. Such colorings arise in a natural way when clustering, indexing and bounding space for various genetic data for efficient analysis. We discuss the corresponding chromatic number and derive an upper bound as a function of the maximum number of descendants of a given vertex and the inductiveness of the corresponding hypergraph, which is obtained from the original digraph. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-25959-6_22 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
relational databases,multidimensional clustering,indexing,bitmap indexing,vertex coloring,digraph,acyclic digraph,poset,hypergraph,ancestor,descendant,down-set | Complete coloring,Discrete mathematics,Combinatorics,Vertex (geometry),Fractional coloring,Upper and lower bounds,Hypergraph,Overline,Partially ordered set,Digraph,Mathematics | Conference |
Volume | ISSN | Citations |
3062 | 0302-9743 | 2 |
PageRank | References | Authors |
0.40 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Geir Agnarsson | 1 | 103 | 14.69 |
| Ágúst S. Egilsson | 2 | 4 | 1.17 |
| Magnús M. Halldórsson | 3 | 2436 | 241.34 |