Name
Abstract | ||
|---|---|---|
We investigate the problem of finding an unknown cut through querying vertices of a graph G. Our complexity measure is the number of submitted queries. To avoid some worst cases, we make a few assumptions which allow us to obtain an algorithm with the worst case query complexity of O(k) + 2k log n/k in which k is the number of vertices adjacent to cut-edges. We also provide a matching lowerbound and then prove if G is a tree our algorithm can asymptotically achieve the information theoretic lowerbound on the query complexity. Finally, we show it is possible to remove our extra assumptions but achieve an approximate solution. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73545-8_45 | COCOON |
Keywords | Field | DocType |
query complexity,complexity measure,approximate solution,worst case query complexity,worst case,matching lowerbound,information theoretic lowerbound,log n,extra assumption,graph g.,vertex query,unknown cut | Binary logarithm,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Computer science,Information complexity,Approximate solution | Conference |
Volume | ISSN | ISBN |
4598 | 0302-9743 | 3-540-73544-5 |
Citations | PageRank | References |
4 | 0.52 | 11 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peyman Afshani | 1 | 256 | 23.84 |
| Ehsan Chiniforooshan | 2 | 118 | 16.38 |
| Reza Dorrigiv | 3 | 176 | 14.02 |
| Arash Farzan | 4 | 136 | 11.07 |
| Mehdi Mirzazadeh | 5 | 13 | 1.74 |
| Narges Simjour | 6 | 36 | 2.85 |
| Hamid Zarrabi-Zadeh | 7 | 111 | 13.63 |