Innovative concept of the strict line hypergraph as the basis for specifying the duality relation between the vertex separators and cuts
Abstract:
This article presents the original approach for establishing the duality relation between the vertex separators and cuts in hypergraphs. The analysis of the existing mathematical structures providing the edge-focused representation of graphs is followed by the identification of the fundamental drawbacks obstructing the formation of the duality relation on the basis of these structures. With a view to filling this research gap, the article formulates the core concept of the strict line hypergraph and introduces the new notions of the degenerate connected components and vertex separators. The proposed structures underlie the construction of the duality relation between the vertex separators and cuts in the form of theorems accompanied with their rigorous proofs and discussions of the specific situations. Finally, the article considers the application of the established relation for linking the combinatorial optimization problems whose solution spaces are composed of the vertex separators and cuts.
References:
Goh, C.J., Yang, X.Q.: Duality in Optimization and Variational Inequalities. Taylor & Francis, London (2002)
View in Google ScholarPotebnia, A.: Representation of the greedy algorithms applicability for solving the combinatorial optimization problems based on the hypergraph mathematical structure. In: Proceedings of 14th International Conference on the Experience of Designing and Application of CAD Systems in Microelectronics (CADSM), pp. 328–332. IEEE, Lviv (2017)
View in Google ScholarHolme, P., Kim, B.J., Yoon, C.N., Han, S.K.: Attack vulnerability of complex networks. Phys. Rev. E 65(5), 056109 (2002)
View in Google ScholarPotebnia, A.: Method for classification of the computational problems on the basis of the multifractal division of the complexity classes. In: Proceedings of 3rd International Scientific-Practical Conference on Problems of Infocommunications, Science and Technology (PIC S&T), pp. 1–4. IEEE, Kharkiv (2016)
View in Google ScholarSchaub, M.T., Lehmann, J., Yaliraki, S.N., Barahona, M.: Structure of complex networks: quantifying edge-to-edge relations by failure-induced flow redistribution. Netw. Sci. 2(1), 66–89 (2014)
View in Google ScholarGanesan, A.: Performance of sufficient conditions for distributed quality-of-service support in wireless networks. Wirel. Netw. 20(6), 1321–1334 (2014)
View in Google ScholarLu, Z., Li, X.: Attack vulnerability of network controllability. PLoS ONE 11(9), e0162289 (2016)
View in Google ScholarShen, Y., Nguyen, N.P., Xuan, Y., Thai, M.T.: On the discovery of critical links and nodes for assessing network vulnerability. IEEE/ACM Trans. Netw. 21(3), 963–973 (2013)
View in Google ScholarRay, S.S.: Planar and dual graphs. In: Graph Theory with Algorithms and its Applications, pp. 135–158. Springer, India (2013)
View in Google ScholarAhuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, New Jersey (1993)
View in Google ScholarXicheng, L., Li, Q.: Line graphs of pseudographs. In: Proceedings of the International Conference on Circuits and Systems, pp. 713–716. IEEE, Shenzhen (1991)
View in Google ScholarEvans, T., Lambiotte, R.: Line graphs, link partitions, and overlapping communities. Phys. Rev. E 80(1), 016105 (2009)
View in Google ScholarHuggett, S., Moffatt, I.: Bipartite partial duals and circuits in medial graphs. Combinatorica 33(2), 231–252 (2013)
View in Google ScholarBrylawski, T., Oxley, J.G.: The Tutte polynomial and its applications. In: White, N. (ed.) Matroid Applications, pp. 123–225. Cambridge University Press, Cambridge (1992)
View in Google ScholarPotebnia, A.: Creation of the mathematical apparatus for establishing the duality relation between the vertex separators and cuts in hypergraphs. In: Proceedings of 12th International Scientific and Technical Conference on Computer Science and Information Technologies (CSIT), pp. 236–239. IEEE, Lviv (2017)
View in Google Scholar
