| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9952155 | Information Processing Letters | 2018 | 5 Pages |
Abstract
In this paper, we update this Hasse diagram by showing that, while for every integer d such that d=3k or d=3k+2, where kâ¥1, the ED problem remains NP-complete for graphs of diameter d, the weighted version of the problem is solvable in time O(|V(G)|+|E(G)|) in the class of diameter three bipartite graphs and in time O(|V(G)|5) in the class of diameter three planar graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
G. Abrishami, F. Rahbarnia,