Vol. 60 No. 2 (270) (2026): In process

DOI: https://doi.org/10.46991/PYSUA.2026.60.2
Published: 2026-06-16

Mathematics

  • Mathematics

    ON EDGE-CHROMATIC SUMS OF CORONA PRODUCTS OF GRAPHS

    Hamlet V. Mikaelyan, Petros A. Petrosyan
    View PDF
    Abstract

    A proper edge-coloring of a graph $G$ is a mapping from its edges to the set of positive integers, so that adjacent edges receive different numbers (colors). If a proper edge-coloring of a graph $G$ minimizes the sum of colors on all edges, it is called a sum edge-coloring and the sum is called the edge-chromatic sum of $G$. In this paper, we study the connection between the edge-chromatic sum of corona product of graphs with the edge-chromatic sums of its factors.  We provide general upper bounds on the edge-chromatic sum of corona products of graphs, as well as we prove that the edge-chromatic sum of the corona products of bipartite graphs and regular graphs of odd order can be exactly determined by the edge-chromatic sums of the factors.

    References

    West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey (2001). https://dwest.web.illinois.edu/igt/

    Supowit K.J. Finding a Maximum Planar Subset of a Set of Nets in a Channel. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 6 (1987), 93-94. https://doi.org/10.1109/TCAD.1987.1270250

    Kubicka E. The Chromatic Sum and Efficient Tree Algorithms. PhD Thesis. Western Michigan University (1989).

    Giaro K., Janczewski R., et al. A 27/26-approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs. Lecture Notes in Computer Science. 2462 (2002), 135-145. https://doi.org/10.1007/3-540-45753-4_13

    Jansen K. The Optimum Cost Chromatic Partition Problem. Algorithms and Complexity. Springer, Berlin (1997), 25-36.

    Kubicka E., Kubicki G., Kountanis D. Approximation Algorithms for the Chromatic Sum. In: Lecture Notes in Comput. Sci. 507 (1991), 15-21. https://doi.org/10.1007/BFb0038467

    Malafiejski M., Giaro K., et al. Sum Coloring of Bipartite Graphs with Bounded Degree. Algorythmica 40 (2004), 235-244. https://doi.org/10.1007/s00453-004-1111-4

    Thomassen C., Erdos P., et al. Tight Bounds on the Chromatic Sum of a Connected Graph. J. Graph Theory 13 (1989), 353-357. https://doi.org/10.1002/jgt.3190130310

    Lecat C., Lucet C., Li C.-M. New Lower Bound for the Minimum Sum Coloring Problem. In: Proc. AAAI Conf. Artificial Intelligence (2017), 853-859. https://doi.org/10.1609/aaai.v31i1.10661

    Moukrim A., Sghiouer K. et al. Upper and Lower Bounds for the Minimum Sum Coloring Problem. International Symposium on Combinatorial Optimization (ISCO2010) (2013).

    Hajiabolhassan H., Mehrabadi M.L., Tusserkani R. Minimal Coloring and Strength of Graphs. Discrete Math. 215 (2000), 265-270. https://doi.org/10.1016/S0012-365X(99)00319-2

    Bar-Noy A., Bellare M., et al. On Chromatic Sums and Distributed Resource Allocation. Inform. and Comput. 140 (1998), 183-202. https://doi.org/10.1006/inco.1997.2677

    Salavatipour M.R. On Sum Coloring of Graphs. Discrete Appl. Math. 127 (2003), 477-488. https://doi.org/10.1016/S0166-218X(02)00249-4

    Marx D. Complexity Results for Minimum Sum Edge Coloring. Discrete Appl. Math. 157 (2009), 1034-1045. https://doi.org/10.1016/j.dam.2008.04.002

    Giaro K., Kubale M. Edge-Chromatic Sum of Trees and Bounded Cyclicity Graphs. Inform. Process. Lett. 75 (2000), 65-69. https://doi.org/10.1016/S0020-0190(00)00072-7

    Petrosyan P.A., Kamalian R.R. On Sum Edge-Coloring of Regular, Bipartite and Split Graphs. Discrete Appl. Math.bf 165 (2014), 263-269. https://doi.org/10.1016/j.dam.2013.09.025

    Mitchem J., Morriss P., Schmeichel E.F. On the Cost Chromatic Number of Outerplanar, Planar, and Line Graphs. Discuss. Math. Graph Theory 17 (1997), 229-241. https://doi.org/10.7151/DMGT.1050

    Frucht R., Harary F. On the Corona of Two Graphs. Aequationes Math. 4 (1970), 322-325. https://doi.org/10.1007/BF01844162

    Sharma R., Adhikari B., Mishra A. Structural and Spectral Properties of Corona Graphs. Discrete Appl. Math. 228 (2017), 14-31. https://doi.org/10.1016/j.dam.2017.01.005

    Arumugam S., Lee Yi-Chun et al. On Local Antimagic Vertex Coloring for Corona Products of Graphs. Combinatorics (2018). https://arxiv.org/abs/1808.04956

    Thiru V.S., Balaji S. Strong Chromatic Indices of Certain Binary Operations on Graphs. Discrete Math. Algorithms Appl. 16 (2024), 2350073. https://doi.org/10.1142/S1793830923500738

    Izbicki H. Zulässige Kantenfärbungen von Pseudo-regulären Graphen mit Minimaler Kantenfarbenzahl. Monatsh. Math. 67 (1963), 25-31. https://doi.org/10.1007/BF01300678

Informatics

  • Informatics

    PARALLEL 3D RECTILINEAR STEINER TREE CONSTRUCTION BASED ON SPANNING GRAPHS

    Rafayel N. Khachatryan
    View PDF
    Abstract

    Steiner tree construction is a fundamental problem in VLSI physical design. Given a set of pins in 3D space, the objective is to connect all pins with minimum total wirelength, possibly using additional Steiner points. This problem becomes particularly important in modern 3D integrated circuits, where vertical connections are realized through Through-Silicon Vias (TSVs). Since TSVs occupy valuable silicon area, their positions must be carefully determined and tracked to avoid conflicts between different nets. Building upon the 3D rectilinear spanning graph presented in prior work, this paper proposes a parallel algorithm for 3D rectilinear Steiner tree construction. The main contributions are as follows. First, the pair-generation process is decoupled from Kruskal's algorithm. Second, Tarjan's sequential lowest-common-ancestor (LCA) computation is replaced with the Euler tour technique combined with a range-minimum-query (RMQ) data structure, enabling fast and independent parallel LCA queries. In addition, a centroid-based tree partitioning scheme is introduced, which allows edge substitutions to be computed concurrently and independently. The proposed algorithm achieves up to $15\times$ speedup with 16 threads compared to the sequential version while maintaining solution quality. As an application, a TSV-aware multi-net routing framework is demonstrated, where dies are modeled as layers in 3D space, and TSV positions are dynamically determined during Steiner tree construction and tracked to prevent conflicts between nets.

    References

    Garey M.R., Johnson D.S. The Rectilinear Steiner Tree Problem is NP-Complete. SIAM Journal on Applied Mathematics 32 (1977), 826-834. https://doi.org/10.1137/0132071

    Zhou H., Shenoy N., Nicholls W. Efficient Minimum Spanning Tree Construction without Delaunay Triangulation. Proc. Asia South Pacific Design Automation Conf. (ASP-DAC) (2001), 25-30. https://doi.org/10.1016/S0020-0190(01)00232-0

    Zhou H. Efficient Steiner Tree Construction Based on Spanning Graphs. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 23 (2004), 704-710. https://doi.org/10.1109/TCAD.2004.826557

    Zhu Q., Zhou H., et al. Spanning Graph-based Nonrectilinear Steiner Tree Algorithms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 24 (2005), 1066-1075. https://doi.org/10.1109/TCAD.2005.850862

    Long J., Zhou H., Memik S.O. EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction Algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27 (2008), 2169-2182. https://doi.org/10.1109/TCAD.2008.2006098

    Lin C.-W., Chen S.-Y., et al. Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27 (2008), 643-653. https://doi.org/10.1109/TCAD.2008.917583

    Lin C.-W., Huang S.-L., et al. Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27 (2008), 2007-2016. https://doi.org/10.1109/TCAD.2008.2006095

    Wang R.-Y., et al. Efficient Multi-Layer Obstacle-Avoiding Region-to-Region Rectilinear Steiner Tree Construction. Proceedings of the 55th ACM/ESDA/IEEE Design Automation Conference (DAC). USA, CA, San Francisco (2018), 1-6.

    Lee M.C., Jan G.E., Luo C.C. An Efficient Rectilinear and Octilinear Steiner Minimal Tree Algorithm for Multidimensional Environments. IEEE Access 8 (2020), 48141-48150. https://doi.org/10.1109/ACCESS.2020.2977825

    Lin S.-E.D., Kim D.H. Construction of All Multilayer Monolithic Rectilinear Steiner Minimum Trees on the 3D Hanan Grid for Monolithic 3D IC Routing. Proceedings of the International Symposium on Physical Design (ISPD) (2019), 57-64. https://doi.org/10.1145/3299902.3309749

    Yan J.-T., Chen Z.-W., Hu D.-H. Timing-driven Steiner Tree Construction for Three-dimensional ICs. Proceedings of the IEEE International Conference on IC Design Technology (2008), 335-338. https://doi.org/10.1109/NEWCAS.2008.4606389

    Tang H., Liu G., et al. A Survey on Steiner Tree Construction and Global Routing for VLSI Design. IEEE Access 8 (2020), 68593-68622. https://doi.org/10.1109/ACCESS.2020.2986138

    Khachatryan R.N., Harutyunyan A.G. Parallelization of Rectilinear Minimum Spanning Tree Construction Algorithm. Proceedings of ISPC ``Modern Information and Electronic Technologies". Ukraine, Odesa (2025), 35-36. https://arar.sci.am/Content/427647/121-128.pdf

    Harutyunyan A.G., Khachatryan R.N. ``Coarse-Grained Parallelization of the Spanning Graph Construction Algorithm. Proc. of the RA NAS and NPUA, Ser. of Technical Sciences 78 (2025), 121-128. https://doi.org/10.53297/0002306X-2025.v78.1-121

    Cormen T.H., Leiserson C.E., Rivest R.L. Introduction to Algorithms. Cambridge, MA, MIT Press (1989). https://doi.org/10.5555/1614191