Name
Abstract | ||
|---|---|---|
Given a connected weighted graph G = (V,E), we consider a hypergraph HG = (V, PG) corresponding to the set of all shortest paths in G. For a given real assignment a on V satisfying 0≤a(v)≤1, a global rounding α with respect to HG is a binary assignment satisfying that |Σv∈Fa(v)-α(v)| F ∈ PG. We conjecture that there are at most |V| + 1 global roundings for HG, and also the set of global roundings is an affine independent set. We give several positive evidences for the conjecture. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.tcs.2004.02.044 | Theoretical Computer Science - Special papers from: COCOON 2003 |
Keywords | DocType | Volume |
05c65,shortest path,combinatorics,rounding,hypergraph hg,05c90,68q25,hypergraph,positive evidence,68q20,global rounding,affine independent set,graph,global roundings,real assignment,discrepancy,binary assignment,connected weighted graph,satisfiability,independent set | Journal | 325 |
Issue | ISSN | ISBN |
3 | 0304-3975 | 3-540-40534-8 |
Citations | PageRank | References |
5 | 0.64 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tetsuo Asano | 1 | 1448 | 229.35 |
| naoki katoh | 2 | 1101 | 187.43 |
| Hisao Tamaki | 3 | 1098 | 105.17 |
| Takeshi Tokuyama | 4 | 1179 | 417.31 |