Name
Abstract | ||
|---|---|---|
A unit bar-visibility graph is a graph whose vertices can be represented in the plane by disjoint horizontal unit-length bars such that two vertices are adjacent if and only if there is a unobstructed, non-degenerate, vertical band of visibility between the corresponding bars. We generalize unit bar-visibility graphs to [1, k]-bar-visibility graphs by allowing the lengths of the bars to be between Ilk and 1. We completely characterize these graphs for trees. We establish an algorithm with complexity O(kn) to determine whether a tree with n vertices has a [1, k]-bar-visibility representation. In the course of developing the algorithm, we study a special case of the knapsack problem: Partitioning a set of positive integers into two sets with sums as equal as possible. We give a necessary and sufficient condition for the existence of such a partition. |
Year | Venue | Keywords |
|---|---|---|
2006 | ELECTRONIC JOURNAL OF COMBINATORICS | knapsack problem |
Field | DocType | Volume |
Integer,Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Chordal graph,Independent set,Knapsack problem,Partition (number theory),Mathematics,Special case | Journal | 13 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 3 |
PageRank | References | Authors |
0.43 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guantao Chen | 1 | 3 | 0.43 |
| Joan P. Hutchinson | 2 | 345 | 68.64 |
| Ken Keating | 3 | 3 | 0.43 |
| Jian Shen | 4 | 92 | 14.67 |