網路通常透過圖來表示，其中頂點對應於處理器，邊對應於處理器之間的通訊。由於對大型圖分析的需求不斷增加，子圖最佳化問題已成為一個活躍且最重要的研究領域。在本篇論文中，我們考慮與以下主題相關的子圖最佳化問題：網路的獨立生成樹、最密集的k 子圖問題、使用距離監控圖的邊以及中繼站定位問題。本篇論文對現有文獻有多種貢獻。

網路的獨立生成樹 在網路中使用多個獨立生成樹(ISTs) 進行數據廣播具有許多優勢，包括提高容錯性和安全訊息分散。因此，在網絡上設計多個獨立生成樹已被廣泛研究。Kao 等人[Journal of Combinatorial Optimization 38 (2019) 972-986] 提出了一種在氣泡排序網路中建構獨立生成樹的演算法。此演算法使用遞迴函數，因此難以平行化。在本篇論文中，我們研究在氣泡排序網絡Bn 中建構ISTs 的問題，並提出了一種非遞迴的演算法。我們的方法可以完全並行化，即每個頂點都可以在常數時間內確定每個生成樹中的父節點。這解決了Kao 等人的問題。此外，也證明了我們算法的總時間複雜度O(n · n!) 是漸近最優的，其中n 是Bn 的維度，n! 是網路的頂點數。

最密集的k 子圖問題 各種現實世界的系統可以模擬成圖形表示。社交網絡、通訊網絡、全球資訊網社群、生物信息學中的許多應用都與從大圖中找到密集子圖有關。一個完整的加權圖G = (V,E,w) 稱為Δβ 度量圖，對於某些β ≥ 1/2，如果G滿足β 三角形不等式，即w(u, v) ≤ β · (w(u, x)+w(x, v)) 對於所有頂點u, v, x ∈ V。給定一個Δβ 度量圖G = (V,E,w)，Δβ 加權最密集k 子圖問題是找到具有恰好k個頂點的引導子圖G[C]，使得G[C] 的總邊權重最大，其中C 是V 的頂點子集。對於β = 1，這個問題Δ 加權最密集k 子圖是已知的非確定性多項式難題，並承認1/2近似算法。在本篇論文中，我們表明對於任何β > 1/2，Δβ 加權最密集k 子圖非確定性多項式難題。我們證明Δβ 加權最密集k 子圖可以近似為( 1/2β + 2β−1/2β·(2k−3) )對於任何β > 1/2。此外，我們展示如何修改任何α 近似算法對於Δ 加權最密集k子圖以獲得δα,β近似演算法對於Δβ 加權最密集k 子圖的演算法對於1/2 < β < 1。

使用距離監控圖的邊 測量圖中距離的探針存在於現實生活的網路中，這在尋找路徑的任務中很有用。它們也經常用於有關網絡驗證的問題。我們在網絡監控領域引入了一個新的圖論概念。圖G 的頂點集M 是一個距離監控的邊集合，如果對於圖G 的每條邊e都有一個頂點x 和一個G 的頂點y 使得e 屬於x 和y 之間的所有最短路徑，我們用dem(G)來表示G 中此類集合的最小集合。M 的頂點表示圖G 在網絡中的距離探針； 當邊e 故障時，從x 到y 的距離增加，因此我們能夠檢測到故障的邊。事實證明，我們不僅可以檢測到它，甚至可以正確定位故障的邊。在本篇論文中，我們開始對此新概念進行研究。我們表明，對於n 的非平凡連通圖G，1 ≤ dem(G) ≤ n−1 且dem(G) = 1 若且唯若G 是一棵樹，並且dem(G) = n−1若且唯若是一個完全圖。我們為網格、超立方體和完整的二分圖計算dem 的精確值。然後，我們將dem 與其他標準圖形參數相關聯。我們證明dem(G) 的下界是圖的最小森林數，上界是它的頂點覆蓋數。我們表明，圖G 確定dem(G) 是一個非確定性多項式完全問題，即使對於頂點圖也是如此。現在已存在多項式時間對數因子近似算法，但是計算漸近更好的近似演算法是非確定性多項式難題，即使對於小直徑的二分圖和二分圖子圖也是如此。對於這種情況，當依照解決方案大小參數化時，此問題不太可能是固定參數可解決的。

中繼站定位問題 中繼站定位問題(HLP) 的設計在交通領域有很多應用。網絡中的每個集線器都有自己的最大傳輸速率和建設成本。中繼站定位問題起源於電信和交通系統。它們結合了各個方面的網路問題，包括位置問題、網路設計問題和路徑問題。這些問題主要是通過中繼站的子集路徑服務，而不是通過需求節點之間的直接鏈接。因此，中繼站定位問題的解決方案通常使用中繼站路徑服務並嘗試降低構建服務鏈接的成本。在本篇論文中，我們對中繼站定位問題進行了調查。我們對問題進行了分類，並提出中繼站定位問題不同的基本模型。我們回顧了一些在以前的論文中沒有考慮過的模型。此外，還介紹了一些解決方法。

Networks are often modeled by graphs, in which a vertex corresponds to a processor and an edge corresponds to a communication link between the processors. Due to the increasing requirement for large graph analysis, subgraph optimization problems have become an active and most significant research area. In this thesis, we consider subgraph optimization problems related to the following topics : independent spanning trees in networks, the densest k-subgraph problem, monitoring the edges of a graph using distances, and hub location problems. There are several ways in which this thesis contributes to the existing literature.

Independent spanning trees in networks. The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. [Journal of Combinatorial Optimization 38 (2019) 972-986] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this thesis, we focus on the problem of constructing ISTs in bubble-sort networks Bn and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O(n · n!) of our algorithm is asymptotically optimal, where n is the dimension of Bn and n! is the number of vertices of the network.

Densest k-subgraph problem. Various real-world systems can be modeled as graphbased representation. Many applications in social networks, communication networks, mobile ad hoc networks, World Wide Web (WWW) communities, bioinformatics are related to nd a dense subgraph from a large graph. A complete weighted graph G = (V,E,w) is called Δβ-metric, for some β ≥ 1/2, if G satises the β-triangle inequality, i.e., w(u, v) ≤ β · (w(u, x)+w(x, v)) for all vertices u, v, x ∈ V . Given a Δβ-metric graph G = (V,E,w), the Δβ-Weighted Densest k-Subgraph (Δβ-WDkS) problem is to nd an induced subgraph G[C] with exactly k vertices such that the total edge weight of G[C] is maximized, where C is a vertex subset of V. For β = 1, this problem, Δ-WDkS, is known NP-hard and admits a 1
2-approximation algorithms. In this thesis, we show that for any β > 1/2, Δβ-WDkS is NP-hard. We prove that Δβ-WDkS can be approximated to within a factor ( 1/2β + 2β−1/2β·(2k−3) ) for any β > 1/2 . Moreover, we show how to modify any α-approximation algorithm for Δ-WDkS to obtain a δα,β-approximation algorithm for Δβ-WDkS for every 1/2 < β < 1.

Monitoring the edges of a graph using distances. Probes that measure distances in graphs are present in real-life networks, for instance this is useful in the fundamental task of routing. They are also frequently used for problems concerning network verification. We introduce a new graph-theoretic concept in the area of network monitoring. A set M of vertices of a graph G is a distance-edge-monitoring set if for every edge e of G, there is a vertex x of M and a vertex y of G such that e belongs to all shortest paths between x and y. We denote by dem(G) the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G; when the edge e fails, the distance from x to y increases, and thus we are able to detect the failure. It turns out that not only we can detect it, but we can even correctly locate the failing edge. In this thesis, we initiate the study of this new concept. We show that for a nontrivial connected graph G of order n, 1 ≤ dem(G) ≤ n − 1 with dem(G) = 1 if and only if G is a tree, and dem(G) = n − 1 if and only if it is a complete graph. We compute the exact value of dem for grids, hypercubes, and complete bipartite graphs. Then, we relate dem to other standard graph parameters. We show that dem(G) is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number. We show that determining dem(G) for an input graph G is an NP-complete problem, even for apex graphs. There exists a polynomial-time logarithmic-factor approximation algorithm, however it is NP-hard to compute an asymptotically better approximation, even for bipartite graphs of small diameter and for bipartite subcubic graphs. For such instances, the problem is also unlikey to be fixed parameter tractable when parameterized by the solution size.

Hub location problems. The design of hub location problems (HLPs) has many applications in transportation. Each hub in the network has its own maximal transmission rate and construction cost. Hub location problems originated in telecommunications and transportation systems. They combine various aspects of network issues, including location problems, network design problems and routing problems. The main them of these problems is to route the services via a subset of hubs, rather than route each service with direct links between demand nodes. Therefore, solutions for hub location problems typically use sets of hubs to reroute the ow of the services and attempt to reduce the costs of building the service links. In this thesis, we present a survey of hub location problems. We classify the problems, and present the basic models for different variations of HLPs. In addition, we review some models that have not been considered in previous review papers. Also, some solution approaches are presented.

[1] S. B. Akers, B. Krishnamurty, A group theoretic model for symmetric interconnection networks, IEEE Transactions on Computers, vol. 38, no. 4, pp. 555--566, 1989.
[2] S. Alumur, B. Y. Kara, Network hub location problems: the state of the art, European Journal of Operational Research, vol. 190, no. 1, pp. 1--21, 2008.
[3] S. A. Alumur, S. Nickel, B. Rohrbeck, F. Saldanha-da-Gama, Modeling congestion and service time in hub location problems, Applied Mathematical Modelling, vol. 55, pp. 13--32, 2018.
[4] T. Andreae, On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality, Networks, vol. 38, pp. 59--67, 2001.
[5] T. Andreae, H.-J. Bandelt, Performance guarantees for approximation algorithms depending on parameterized triangle inequalities, SIAM Journal on Discret Mathematics, vol. 8, pp. 1--16, 1995.
[6] T. Araki, Y. Kikuchi, Hamiltonian laceability of bubble-sort graphs with edge faults, Information Sciences, vol. 177, no. 13, pp, 2679--2691, 2007.
[7] S. Arora, D. Karger, M. Karpinski, Polynimial time approximation schemes for dense instances of NP-hard problems, In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 284--293, 1995.
[8] Y. Asahiro, K. Iwama, H. Tamaki, T. Tokuyama, Greedily nding a dense subgraph,Journal of Algorithms, vol. 34, pp. 203--221, 2000.
[9] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and approximation: combinatorial optimization problems and their approximability properties, 1999.
[10] T. Aykin, Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem, European Journal of Operational Research, vol. 79, no. 3, pp. 501--523, 1994.
[11] J. Backer, J. M. Keil, Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs, Information Processing Letters, vol. 110, pp. 635--638, 2010.
[12] E. Bampas, D. Bilò, G. Drovandi, L. Gualà, R. Klasing, G. Proietti, Network verification via routing table queries, Journal of Computer and System Sciences, vol 81, no. 1, pp. 234--248, 2015.
[13] F. Bao, Y. Funyu, Y. Hamada, Y. Igarashi, Reliable broadcasting and secure distributing in channel networks, In Proceedings of 3rd International Symposium on Parallel Architectures, Algorithms and Networks, pp. 472--478, 1997.
[14] J. Baste, F. Beggas, H. Kheddouci, I. Sau, On the parameterized complexity of the edge monitoring problem, Information Processing Letters, vol. 121, pp. 39--44, 2017.
[15] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Ho mann, M. Mihalák, L. S. Ram, Network discovery and veri cation, IEEE Journal on Selected Areas in Communications, vol 24, no. 12, pp. 2168--2181, 2006.
[16] Y. Bejerano, R. Rastogi, Robust monitoring of link delays and faults in IP networks, IEEE/ACM Transactions on Networking, vol 14, no. 5, pp. 1092--1103, 2006.
[17] M.A. Bender, C. Chekuri, Performance guarantees for the TSP with a parameterized triangle inequality, Information Processing Letters, vol. 73 (2000), pp. 17--21.
[18] A. Bhaskara, M. Charika, E. Chlamtac, U. Feige, A. Vijayaraghavan, Detecting high log-densities: an O(n1/4)-approximation algorithms for the densest ksubgraph, In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC'10), pp. 201--210, 2010.
[19] D. Bilò, T. Erlebach, M. Mihalák, P. Widmayer, Discovery of network properties with all-shortest-paths queries, Theoretical Computer Science, vol. 411, pp. 1626--1637, 2010.
[20] B. E. Birnbaum, K. J. Goldman, An improved analysis for a greedy remoteclique algorithm using factor-revealing LPs, Algorithmica, vol. 55, no. 1, pp. 42--59, 2009.
[21] M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest, R. E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, vol. 7, pp. 448--461, 1973.
[22] H. J. Böckenhauer, J. Hromkovi c, R. Klasing, S. Seibert, W. Unger, Approximation algorithms for the TSP with sharpened triangle inequality, Information Processing Letters, vol. 75, pp. 133--138, 2000.
[23] H. J. Böckenhauer, S. Seibert, Improved lower bounds on the approximability of the traveling salesman problem, Theoretical Informatics and Applications, vol. 34, pp. 213--255, 2000.
[24] H. J. Böckenhauer, J. Hromkovi£, R. Klasing, S. Seibert, W. Unger, Towards the Notion of Stability of approximation for hard optimization tasks and the traveling salesman Problem (Extended Abstract). Proc. CIAC 2000, LNCS 1767, Springer 2000, pp. 72--86. Full version in Theoretical Computer Science, vol. 285, pp. 3--24, 2002.
[25] H. J. Böckenhauer, J. Hromkovi£, R. Klasing, S. Seibert, W. Unger, An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality, In Annual Symposium on Theoretical Aspects of Computer Science, LNCS 1770, pp. 382--394, 2000.
[26] H. J. Böckenhauer, D. Bongartz, J. Hromkovi£, R. Klasing, G. Proietti, S. Seibert, W. Unger, On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality, Proc. FSTTCS 2002, LNCS 2556, Springer 2002, pp. 59--70, Full version in Theoretical Computer Science, vol. 326, pp. 137--153, 2004.
[27] H. J. Böckenhauer, D. Bongartz, J. Hromkovi£, R. Klasing, G. Proietti, S. Seibert, W. Unger, On k-edge-connectivity problems with sharpened triangle inequality, In proc. 5th Italian Conference on Algorithms and Complexity, pp. 189--200, 2003.
[28] H. J. Böckenhauer, J. Hromkovi£, S. Seibert, Stability of approximation, In: T. F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC, Chapter 31, 2007.
[29] H. J. Böckenhauer, D. Bongartz, J. Hromkovi£, R. Klasing, G. Proietti, S. Seibert, W. Unger, On k-connectivity problems with sharpened triangle inequality, Journal of Discrete Algorithms, vol. 6, pp. 605--617, 2008.
[30] N. Boland, M. Krishnamoorthy, A. T. Ernst, J. Ebery, Preprocessing and cutting for multiple allocation hub location problems, European Journal of Operational Research, vol 155, no. 3, 638-653, 2004.
[31] N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V. Th. Paschos, Exact and superpolynomial approximation algorithms for the densest k-subgraph problem, European Journal of Operational Research, vol. 262, pp. 894--903, 2017.
[32] J. Brimberg, N. Mladenovi¢, R. Todosijevi¢, D. Uro²evi¢, General variable neighborhood search for the uncapacitated single allocation p-hub center problem, Optimization Letters, vol 11, no. 2, pp. 377--388, 2017.
[33] J. F. Campbell, Hub location problems and the p-hub median problem, Center for Business and Industrial Studies, University of Missouri -- St. Louis, St. Louis, MO, 1991.
[34] J. F. Campbell, Integer programming formulations of discrete hub location problems, European Journal of Operational Research, vol 72, no. 2, pp. 387--405, 1994.
[35] J.F. Campbell, A.T. Ernst, M. Krishnamoorthy, Hub location problems, In: Drezner, Z., Hamacher, H.W. (Eds.), Facility Location Applications and Theory, Springer, Heidelberg, pp. 373--408, 2002.
[36] A. M. Campbell, T. J. Lowe, L. Zhang, The p-hub center allocation problem, European journal of operational research, vol 176, no. 2, pp. 819--835, 2007. 71
[37] L. Canovas, M. Landete, A. Marin, New formulations for the uncapacitated multiple allocation hub location problem, European Journal of Operational Research, vol 172, pp. 274--292, 2006.
[38] S. Chaharsooghi, F. Momayezi, N. Gha arinasab, An adaptive large neighborhood search heuristic for solving the reliable multiple allocation hub location problem under hub disruptions, International Journal of Industrial Engineering Computations, vol 8, no. 2, pp.191--202, 2017.
[39] S. C. Chang, L. H. Chen, L. J. Hung, S. S. Kao, R. Klasing, The hardness and approximation of the densest k-subgraph problem in parameterized metric graphs, In: Proceedings of 2020 International Computer Symposium, IEEE, pp. 126--130, 2020.
[40] M. S. Chang, L. H. Chen, L. J. Hung, P. Rossmanith, G. H.Wu, Exact algorithms for problems related to the densest k-set problem, Information Processing Letters, vol. 114, 510--513, 2014.
[41] J. M. Chang, J. D. Wang, J. S. Yang, K. J. Pai, A comment on independent spanning trees in crossed cubes, Information Processing Letters, vol. 114, no. 12, pp. 734--739, 2014.
[42] Y. H. Chang, J. S. Yang, J. M. Chang, Y. L. Wang, A fast parallel algorithm for constructing independent spanning trees on parity cubes, Applied Mathematics and Computation, vol. 268, pp. 489--495, 2015.
[43] Y. H. Chang, J. S. Yang, S. Y. Hsieh, J. M. Chang, Y. L. Wang, Construction independent spanning trees on locally twisted cubes in parallel, Journal of Combinatorial Optimization, vol. 33, no. 3, pp. 956--967, 2017.
[44] J. M. Chang, T. J. Yang, J. S. Yang, A parallel algorithm for constructing independent spanning trees in twisted cubes, Discrete Applied Mathematics, vol. 219, pp. 74--82, 2017.
[45] S. Chanta, O. Sangsawang, A single allocation p-hub maximal covering model for optimizing railway station location, In International Conference on Intelligent Computing and Optimization, pp. 522--530, 2018.
[46] D. Z. Chen, R. Fleischer, J. Li, Densest k-subgraph approximation on intersection graphs, In Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA'10), pp. 83--93, 2010.
[47] L. H. Chen, S. Y. Hsieh, L. J. Hung, R. Klasing, The approximability of the p-hub center problem with parameterized triangle inequality, In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), LNCS 10392, pp. 112--123.
[48] L. H. Chen, S.-Y. Hsieh, L.-J. Hung, R. Klasing, C.-W. Lee, B. Y. Wu, On the complexity of the star p-hub center problem with parameterized triangle inequality, The 10th International Conference on Algorithms and Complexity, LNCS 10236, pp. 152--163, 2017. 72
[49] L. H. Chen, D.-W. Cheng, S.-Y. Hsieh, L.-J. Hung, R. Klasing, C.-W. Lee, B. Y. Wu, Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality, Journal of Computer and System Sciences, vol. 92, pp. 92--112, 2018.
[50] L. H. Chen, S.-Y. Hsieh, L.-J. Hung, R. Klasing, Approximation algorithms for the p-hub center routing problem in parameterized metric graphs, Theoretical Computer Science, vol. 806, pp. 271--280, 2020.
[51] J. Chen, B. Chor, M. Fellows, X. Huang, D. W. Juedes, I. A. Kanj, G. Xia, Tight lower bounds for certain parameterized NP-hard problems, Information and Computation, vol 201, no. 2, pp. 216--231, 2005.
[52] D. W. Cheng, C. T. Chan, S. Y. Hsieh, Constructing independent spanning trees on pancake networks, IEEE Access, vol. 8, pp. 3427--3433, 2020.
[53] D. W. Cheng, K. H. Yao, S. Y. Hsieh, Constructing independent spanning trees on generalized recursive circulant graphs, IEEE Access, vol. 9, pp. 74028--74037, 2021.
[54] J. Cheriyan, S. N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms, vol. 9, no. 4, pp. 507--537, 1988.
[55] I. Contreras, J. A. Díaz, E. Fernández, Lagrangean relaxation for the capacitated hub location problem with single assignment, OR spectrum, vol 31, no. 3, pp. 483--505, 2009.
[56] I. Contreras, J. A. Díaz, E. Fernández, Branch and price for large-scale capacitated hub location problems with single assignment, INFORMS Journal on Computing, vol. 23, no. 1, pp. 41--55, 2011.
[57] I. Contreras, M. Tanash, N. Vidyarthi, Exact and heuristic approaches for the cycle hub location problem, Annals of Operations Research, vol. 258, no. 2, pp. 655--677, 2017.
[58] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, 2009.
[59] D. Corneil, Y. Perl, Clustering and domination in perfect graphs, Discrete Applied Mathematics, vol. 9 (1984), pp. 27--40.
[60] S. Curran, O. Lee, X. Yu, Finding four independent trees, SIAM Journal on Computing, vol. 35, no. 5, pp. 1023--1058, 2006.
[61] L. Dall'Asta, J. I. Alvarez-Hamelin, A. Barrat, A. Vázquez, A. Vespignani, Exploring networks with traceroute-like probes: theory and simulations, Theoretical Computer Science, vol. 355, no. 1, pp. 6--24, 2006.
[62] I. Dinur, D. Steurer, Analytical approach to parallel repetition, Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 624--633, 2014. 73
[63] R. G. Downey, M. R. Fellows, Fundamentals of parameterized complexity, springer, 2013.
[64] O. Dukkanci, B. Y. Kara, Routing and scheduling decisions in the hierarchical hub location problem, Computers and Operations Research, vol. 85, pp. 45--57, 2017.
[65] J. Ebery, M. Krishnamoorthy, A. Ernst, N. Boland, The capacitated multiple allocation hub location problem: formulations and algorithms, European Journal of Operational Research, vol. 120, no. 3, pp. 614-631, 2000.
[66] L. Epstein, A. Levin, G. J. Woeginger, The (weighted) metric dimension of graphs: hard and easy cases, Algorithmica, vol. 72, no. 4, pp. 1130--1171, 2015.
[67] A. T. Ernst, M. Krishnamoorthy, An exact solution approach based on shortestpaths for p-hub median problems, INFORMS Journal on Computing, vol. 10, no. 2, pp. 149--162, 1998.
[68] A. T. Ernst, M. Krishnamoorthy, Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem, European Journal of Operational Research, vol. 104, no. 1, pp. 100--112, 1998.
[69] A. T. Ernst, M. Krishnamoorthy, Solution algorithms for the capacitated single allocation hub location problem, Annals of Operations Research, vol. 86, pp. 141--159, 1999.
[70] A. Faragó, Z. R. Mojaveri, In search of the densest subgraph, Algorithms, vol. 12, no. 157, pp. 1--18, 2019.
[71] R. Z. Farahani, M. Hekmatfar, A. B. Arabani, E. Nikbakhsh, Hub location problems: a review of models, classi cation, solution techniques, and applications, Computers and Industrial Engineering, vol. 64, no. 4, pp. 1096--1109, 2013.
[72] U. Feige, M. Seltser, On the dense k-subgraph problem, Technical Report, The Weizmann Institute, 1997.
[73] U. Feige, G. Kortsarz, D. Peleg, The dense k-subgraph problem, Algorithmica, vol. 29, pp. 410--421, 2001.
[74] F. Foucaud, S. S. Kao, R. Klasing, M. Miller, J. Ryan, Monitoring the edges of a graph using distances, Discrete Applied Mathematics, vol. 319, pp. 424--438, 2022.
[75] F. Foucaud, R. Klasing, M. Miller, J. Ryan, Monitoring the Edges of a Graph Using Distances, In Proceeding of the 6th International Conference on Algorithms and Discrete Applied Mathematics, LNCS, vol. 12016, Springer, pp. 28--40, 2020.
[76] M. R. Garey, D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, vol. 32, no. 4, pp. 826--834, 1977. 74
[77] R. Govindan, H. Tangmunarunkit, Heuristics for Internet map discovery, Proceedings of the 19th IEEE International Conference on Computer Communications, INFOCOM'00, pp. 1371--1380, 2000.
[78] H. W. Hamacher, M. Labbé, S. Nickel, T. Sonneborn, Adapting polyhedral properties from facility to hub location problems, Discrete Applied Mathematics, vol. 145, no. 1, pp. 104-116, 2004.
[79] F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combinatoria, vol 2, pp. 191--195, 1976.
[80] H. Hasanzadeh, M. Bashiri, A. Amiri, A new approach to optimize a hub covering location problem with a queue estimation component using genetic programming, Soft Computing, vol. 22, no. 3, pp. 949--961, 2018.
[81] R. Hassin, S. Rubinstein, A. Tamir, Approximation algorithms for maximum dispersion, Operations Research Letters, vol. 21, pp. 133-137, 1997.
[82] A. Ho , J. Peiró, Á. Corberán, R. Martí, Heuristics for the capacitated modular hub location problem, Computers and Operations Research, vol. 86, pp. 94--109, 2017.
[83] J. Hromkovi£, Stability of approximation algorithms and the knapsack problem, In: J. Karhumäki, H. Maurer, G. Paun, G. Rozenberg (Eds.) Jewels are Forever, pp. 238--249, 1999.
[84] J. Hromkovi£, Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, Second Edition , Texts in Theoretical Computer Science, An EATCS Series, 2004.
[85] S. Y. Hsieh, S. S. Kao, A survey of hub location problems, Journal of Interconnection Networks, vol. 19, no. 01, 2019.
[86] J.-F. Huang, E. Cheng, S.-Y. Hsieh, Two algorithms for constructing independent spanning trees in (n, k)-star graphs, IEEE Access, vol. 8, pp. 175932--175947, 2020.
[87] J.-F. Huang, S.-S. Kao, S.-Y. Hsieh, R. Klasing, Top-Down construction of independent spanning trees in alternating group networks, IEEE Access, vol. 8, pp. 112333--112347, 2020.
[88] A. Itai, M. Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation, vol. 79, no. 1, pp. 43--59, 1988.
[89] D. S. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, vol. 9, pp. 256--278, 1974.
[90] R. Klasing, L. J. Hung, S. Y. Hsieh, A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks, In: Proceedings of the 15th International Conference on Algorithmic Aspects in Information and Management, LNCS, vol. 13153, Springer, pp. 252--264, 2021. 75
[91] S. S. Kao, K. J. Pai, S. Y. Hsieh, R. Y. Wu, J. M. Chang, Amortized e ciency of constructing multiple independent spanning trees on bubble-sort networks, Journal of Combinatorial Optimization, vol. 38, no. 3, pp. 972--986, 2019.
[92] B. Y. Kara, B. C. Tansel, The single-assignment hub covering problem: Models and linearizations, Journal of the Operational Research Society, vol. 54, no. 1, pp. 59--64, 2003.
[93] J. M. Keil, T. Brecht, The complexity of clustering in planar graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 9, pp. 155--159, 1991.
[94] A. Kelenc, D. Kuziak, A. Taranenko, I. G. Yero, Mixed metric dimension of graphs, Applied Mathematics and Computation, vol. 314, pp. 429--438, 2017.
[95] A. Kelenc, N. Tratnik, I. G. Yero, Uniquely identifying the edges of a graph: the edge metric dimension, Discrete Applied Mathematics, vol. 251, pp. 204--220, 2018.
[96] L. Kellerhals, T. Koana, Parameterized complexity of geodetic set, Journal of Graph Algorithms and Applications, vol. 26, no. 4, pp. 401--419, 2022.
[97] S. Khot, Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique, SIAM Journal on Computing, vol. 36 (2006), pp. 1025--1071.
[98] Y. Kikuchi, T. Araki, Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs, Information Processing Letter, vol. 100, no. 2, pp. 52--59, 2006.
[99] R. Klasing, T. Mömke, A modern view on stability of approximation, In: Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovi£ on the Occasion of His 60th Birthday, LNCS 11011, pp. 393--408, 2018.
[100] J. G. Klincewicz, Heuristics for the p-hub location problem, European Journal of Operational Research, vol. 53, no. 1, pp. 25--37, 1991.
[101] J.G. Klincewicz, A dual algorithm for the uncapacitated hub location problem, Locatio Science, vol. 4, pp. 173--184, 1996.
[102] T. L. Kung, C. N. Hung, Estimating the subsystem reliability of bubblesort networks, Theoretical Computer Science, vol. 670, pp. 45--55, 2017.
[103] M. Labbé, H. Yaman, E. Gourdin, A branch and cut algorithm for hub location problems with single assignment, Mathematical programming, vol. 102, no. 2, pp. 371--405, 2005.
[104] T. Laihonen, The metric dimension for resolving several objects, Information Processing Letters, vol. 116, no. 11, pp. 694--700, 2016. 76
[105] S. Lakshmivarahan, J. Jwo, S. K. Dhall, Symmetry in interconnection networks based on cayley graphs of permutation groups: a survey, Parallel Computing, vol. 19, no. 4, pp. 361--407, 1993.
[106] F.T. Leighton, Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, Morgan Kaufmann Publishers, 1992.
[107] M. Liazi, I. Milis, V. Zissimopoulos, The densest k-subgraph problem on clique graphs, Journal of Combinatorial Optimization, vol. 14, pp. 465--474, 2007.
[108] M. Liazi, I. Milis, V. Zissimopoulos, A constant approximation algorithm for the densest k-subgraph problem on chordal graphs, Information Processing Letters, vol. 108, pp. 29--32, 2008.
[109] J. C. Lin, J. S. Yang, C. C. Hsu, J. M. Chang, Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes, Information Processing Letters, vol. 110, no. 10, pp. 414--419, 2010.
[110] C. F. Lin, J. F. Huang, S. Y. Hsieh, Constructing independent spanning trees on transposition networks, IEEE Access, vol. 8, pp. 147122--147132, 2020.
[111] L. H. Liu, J. E. Chen, S. Q. Chen, W. J. Jia, An new representation for interconnection network structures, Journal of Central South University of Technology, vol. 9, no. 1, pp. 47--53, 2002.
[112] R. D. Luce, A. Perry, A method of matrix analysis of group structure, Psychometrika, vol. 14, pp. 95--116, 1949.
[113] P. Manuel, S. Klavºar, A. Xavier, A. Arokiaraj, E. Thomas, Strong edge geodetic problem in networks, Open Mathematics, vol. 15, pp. 1225--1235, 2017.
[114] A. Marín, Formulating and solving splittable capacitated multiple allocation hub location problems, Computers and operations research, vol. 32, no. 12, pp. 3093-- 3109, 2005.
[115] G. Mayer, B. Wagner, HubLocator: an exact solution method for the multiple allocation hub location problem, Computers and Operations Research, vol. 29, no. 6, pp. 715--739, 2002.
[116] M. Merakl , H. Yaman, A capacitated hub location problem under hose demand uncertainty, Computers and Operations Research, vol. 88, pp. 58--70, 2017.
[117] T. Mömke, An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality, Information Processing Letters, vol. 115, pp. 866--871, 2015.
[118] R. Niedermeier, Invitation to xed-parameter algorithms, Oxford University Press, 2006.
[119] T. Nonner, PTAS for densest k-subgraph in interval graphs, Proceedings ofWorkshop on Algorithms and Data Structures (WADS 2011), LNCS 6844, pp. 631--641. 77
[120] O. R. Oellermann, J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Applied Mathematics, vol. 155, pp. 356--364, 2007.
[121] M. E. O'Kelly, A quadratic integer program for the location of interacting hub facilities, European Journal of Operational Research, vol. 32, no. 3, pp. 393--404, 1987.
[122] M. E. O'Kelly, Hub facility location with xed costs, Papers in Regional Science, vol. 71, no. 3, pp. 293--306, 1992.
[123] M. Peker, B. Y. Kara, The p-Hub maximal covering problem and extensions for gradual decay functions, Omega, vol. 54, pp. 158--172, 2015.
[124] Z. Qin, Y. Gao, Uncapacitated p-hub location problem with xed costs and uncertain ows, Journal of Intelligent Manufacturing, vol. 28, no. 3, pp. 705--716, 2017.
[125] S. S. Ravi, D. J. Rosenkrantz, G. K. Tayi, Heuristic and special case algorithms for dispersion problems, Operations Research, vol. 42, pp. 299--310, 1994.
[126] A. Seb®, E. Tannier, On metric generators of graphs, Math. Oper. Res., vol. 29, no. 2, pp. 383--393, 2004.
[127] N. Shawash, Relationships among popular interconnection networks and their common generalization, Ph.D. thesis, Oakland University, 2008.
[128] M. R. Silva, C. B. Cunha, A tabu search heuristic for the uncapacitated single allocation p-hub maximal covering problem, European Journal of Operational Research, vol. 262, no. 3, pp. 954--965, 2017.
[129] H. Singh, M. Kumar, P. Aggarwal, Approximation of heaviest k-subgraph problem by size reduction of input graph, In: Krishna C., Dutta M., Kumar R. (eds), Proceedings of 2nd International Conference on Communication, Computing and Networking, Lecture Notes in Networks and Systems, vol 46, pp. 599--606, 2019.
[130] D. Skorin-Kapov, J. Skorin-Kapov, M. O'Kelly, Tight linear programming relaxations of uncapacitated p-hub median problems, European Journal of Operational Research, vol. 94, no. 3, pp. 582--593, 1996.
[131] P. J. Slater, Leaves of trees, Congressus Numerantium, vol. 14, pp. 549--559, 1975.
[132] Y. Suzuki, K. Kaneko, An algorithm for disjoint paths in bubble-sort graphs, Systems and Computers in Japan, vol. 37, pp. 27--32, 2006.
[133] Y. Suzuki, K. Kaneko, The container problem in bubble-sort graphs, IEICE Transactions on Information and Systems, vol. 91, no. 4, pp. 1003--1009, 2008.
[134] M. Tanash, I. Contreras, N. Vidyarthi, An exact algorithm for the modular hub location problem with single assignments, Computers and Operations Research, vol. 85, pp. 32--44, 2017. 78
[135] S. M. Tang, J. S. Yang, Y. L. Wang, J. M. Chang, Independent spanning trees on multidimensional torus networks, IEEE Transactions on Computers, vol. 59, no. 1, pp. 93--102, 2010.
[136] B. Wagner, Model formulations for hub covering problems, Journal of the Operational Research Society, vol. 59, no. 7, pp. 932--938, 2008.
[137] Y. Wang, J. Fan, G. Zhou, X. Jia, Independent spanning trees on twisted cubes, Journal of Parallel and Distributed Computing, vol. 72, no. 1, pp. 58--69, 2012.
[138] M. Wang, Y. Lin, S. Wang, The 2-good-neighbor diagnosability of cayley graphs generated by transposition trees under the PMC model and MM* model, Theoretical Computer Science, vol. 628, pp. 92--100, 2016.
[139] D. B. West, Introduction to graph theory, 2nd Edition, Prentice Hall, 2001.
[140] J. S. Yang, J. M. Chang, S. M. Tang, Y. L. Wang, Reducing the height of independent spanning trees in chordal rings, IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 5, pp. 644--657, 2007.
[141] J. S. Yang, S. M. Tang, J. M. Chang, Y. L.Wang, Parallel construction of optimal independent spanning trees on hypercubes, Parallel Computing, vol. 33, no. 1, pp. 73--79, 2007.
[142] J. S. Yang, J. M. Chang, S. M. Tang, Y. L. Wang, On the independent spanning trees of recursive circulant graphs G(cdm, d) with d > 2, Theoretical Computer Science, vol. 410, no. 21-23, pp. 2001--2010, 2009.
[143] J. S. Yang, J. M. Chang, S. M. Tang, Y. L. Wang, Constructing multiple independent spanning trees on recursive circulant graphs G(2m, 2), International Journal of Foundations of Computer Science, vol. 21, no. 1, pp. 73--90, 2010.
[144] J. S. Yang, H. C. Chan, J. M. Chang, Broadcasting secure messages via optimal independent spanning trees in folded hypercubes, Discrete Applied Mathematics, vol. 159, no. 12, pp. 1254--1263, 2011.
[145] J. S. Yang, J. M. Chang, Optimal independent spanning trees on Cartesian product of hybrid graphs, Computer Journal, vol. 57, no. 1, pp. 93--99, 2014.
[146] J. S. Yang, J. M. Chang, K. J. Pai, H. C. Chan, Parallel construction of independent spanning trees on enhanced hypercubes, IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 11, pp. 3090--3098, 2015.
[147] Y. Yang, S. Wang, J. Li, Subnetwork preclusion for bubble-sort graph networks, Information Processing Letters, vol. 115, no. 11, pp. 817--821, 2015.
[148] J. S. Yang, S. S. Luo, J. M. Chang, Pruning longer branches of independent spanning trees on folded hyper-stars, Computer Journal, vol. 58, no. 11, pp. 2972--2981, 2015. 79
[149] J. S. Yang, M. R. Wu, J. M. Chang, Y. H. Chang, A fully parallelized scheme of constructing independent spanning trees on Möbius cubes, Journal of Supercomputing, vol. 71, no. 1, pp. 894--908, 2015.
[150] Y. C. Yang, S. S. Kao, R. Klasing, S. Y. Hsieh, H. H. Chou, J. M. Chang, The construction of multiple independent spanning trees on burnt pancake networks, IEEE Access, vol. 9, pp. 16679--16691, 2021.
[151] A. Zabihi, M. Gharakhani, A literature survey of hub location problems and methods with emphasis on the marine transportations, Uncertain Supply Chain Management, vol. 6, no. 1, pp. 91-116, 2018.
[152] A. Zehavi, A. Itai, Three tree-paths, Journal of Graph Theory, vol. 13, no. 2, pp. 175--188, 1989.
[153] M. Zhalechian, R. Tavakkoli-Moghaddam,Y. Rahimi, F. Jolai, An interactive possibilistic programming approach for a multi-objective hub location problem: economic and environmental design, Applied Soft Computing, vol. 52, pp. 699-- 713, 2017.
[154] S. L. Zhao, R. X. Hao, The generalized connectivity of (n, k)-bubble-sort graphs, The Computer Journal, vol. 62, no. 9, pp. 1277--1283, 2019.
[155] S. L. Zhao, R. X. Hao, The fault tolerance of (n, k)-bubble-sort networks, Discrete Applied Mathematics, vol. 285, pp. 204--211, 2020.