  Network virtualization provides a promising solution to overcome the
ossification of current networks, allowing multiple Virtual Network Requests
(VNRs) embedded on a common infrastructure. The major challenge in network
virtualization is the Virtual Network Embedding (VNE) problem, which is to
embed VNRs onto a shared substrate network and known to be $\mathcal{NP}$-hard.
The topological heterogeneity of VNRs is one important factor hampering the
performance of the VNE. However, in many specialized applications and
infrastructures, VNRs are of some common structural features $\textit{e.g.}$,
paths and cycles. To achieve better outcomes, it is thus critical to design
dedicated algorithms for these applications and infrastructures by taking into
accounting topological characteristics. Besides, paths and cycles are two of
the most fundamental topologies that all network structures consist of.
Exploiting the characteristics of path and cycle embeddings is vital to tackle
the general VNE problem. In this paper, we investigated the path and cycle
embedding problems. For path embedding, we proved its $\mathcal{NP}$-hardness
and inapproximability. Then, by utilizing Multiple Knapsack Problem (MKP) and
Multi-Dimensional Knapsack Problem (MDKP), we proposed an efficient and
effective MKP-MDKP-based algorithm. For cycle embedding, we proposed a Weighted
Directed Auxiliary Graph (WDAG) to develop a polynomial-time algorithm to
determine the least-resource-consuming embedding. Numerical results showed our
customized algorithms can boost the acceptance ratio and revenue compared to
generic embedding algorithms in the literature.
