On k-Path Covers and their Applications

Provided by: VLD Digital
Topic: Big Data
Format: PDF
The authors introduced the k-all-path cover optimization problem with the goal of computing compact yet faithful synopses of the vertex set of road networks. Their proposed pruning algorithm provides close to optimal results in practice and was experimentally proven to be very efficient on large graphs. For the special subcase of covering all k-node shortest paths as proposed by the researcher, they considerably improved their results in terms of running time and solution quality. But even for covering all paths consisting of k nodes, they could construct surprisingly small cover sets in reasonable time for moderate values of k.

Find By Topic