It is proved that the problem of defining a bounded cost set of nodes S such that the influence spreading from S in G, within a given time bound, is as large as possible, and that the problem is NP-hard, even in simple networks like complete graphs and trees.
This paper develops an exact algorithm based on the Branch and Bound approach for solving PIDS on chordal graphs, which involves identifying the smallest group of vertices in a given network that maximizes influence throughout the network.
Y A Bekhti, M. Lalou, Méziane Aïder et al.· Pesquisa Operacional· 0 citations
It is shown that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 1 citation
This paper shows for both strict and non-strict temporal paths that RTC is NP-complete for any combination of k ≥ 1 and δ ≥ 1 and W [1]-hard for parameter solution size or vertex interval membership width plus pathwidth of the underlying graph.
Jessica A. Enright, Thomas Erlebach, Kitty Meeks et al.· Symposium on Algorithmic Fou...· 0 citations
This work considers the problem of finding, for a given degree sequence, the network structure displaying the smallest possible average shortest-path length and proposes a fast algorithm to construct approximate solutions to such a degree-constrained distance-minimization problem.
