Published January 1, 2021
| Version v1
Publication
A novel approach to find partitions of $ Z_{m} $ with equal sum subsets via complete graphs
- 1. Khwaja Fareed University of Engineering and Information Technology
- 2. University of the Punjab
- 3. King Abdulaziz University
Description
In mathematics and computer sciences, the partitioning of a set into two or more disjoint subsets of equal sums is a well-known NP-complete problem, also referred to as partition problem. There are various approaches to overcome this problem for some particular choice of integers. Here, we use quadratic residue graph to determine the possible partitions of positive integers $ m = 2^{\beta}, q^{\beta}, 2^{\beta}q, $ $ 2q^{\beta}, qp, $ where $ p $, $ q $ are odd primes and $ \beta $ is any positive integer. The quadratic residue graph is defined on the set $ Z_{m} = \{\overline{0}, \overline{1}, \cdots, \overline{m-1}\}, $ where $ Z_{m} $ is the ring of residue classes of $ m $, i.e., there is an edge between $ \overline{x}, $ $ \overline{y}\in Z_{m} $ if and only if $ \overline{x}^{2}\equiv \overline{y}^{2}\; (\text{mod}\; m) $. We characterize these graphs in terms of complete graph for some particular classes of $ m $.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
في الرياضيات وعلوم الكمبيوتر، يعد تقسيم مجموعة إلى مجموعتين فرعيتين منفصلتين أو أكثر من المجاميع المتساوية مشكلة NP كاملة معروفة جيدًا، ويشار إليها أيضًا باسم مشكلة التقسيم. هناك طرق مختلفة للتغلب على هذه المشكلة لاختيار معين من الأعداد الصحيحة. هنا، نستخدم الرسم البياني للمخلفات التربيعية لتحديد الأقسام المحتملة للأعداد الصحيحة الموجبة $ m = 2^{\beta}, q^{\beta}, 2^{\beta}q, $ 2q ^{\beta}, qp, $ حيث $ p $, $ q $ أعداد أولية فردية و $\beta $ أي عدد صحيح موجب. يتم تعريف الرسم البياني للمخلفات التربيعية على المجموعة $ Z _{ m }=\{\ overline{0}, \overline{1}, \cdots,\ overline{m -1}\}, $ حيث $ Z _{ m }$ هي حلقة فئات المخلفات بقيمة $ m $، أي أن هناك حافة بين $\overline{x}, $$\ overline {y}\in Z _{ m }$ إذا وفقط إذا $\ overline{x }^{ 2}\ equiv \overline{y }^{ 2 }\;(\ text{mod}\; m )$. نميز هذه الرسوم البيانية من حيث الرسم البياني الكامل لبعض الفئات المعينة من $ m $.Translated Description (French)
En mathématiques et en informatique, le partitionnement d'un ensemble en deux ou plusieurs sous-ensembles disjoints de sommes égales est un problème NP-complet bien connu, également appelé problème de partition. Il existe diverses approches pour surmonter ce problème pour un choix particulier d'entiers. Ici, nous utilisons le graphique des résidus quadratiques pour déterminer les partitions possibles des entiers positifs $ m = 2^{\beta}, q^{\beta}, 2^{\beta}q, $ $ 2q^{\beta}, qp, $ où $ p $ , $ q $ sont des nombres premiers impairs et $ \beta $ est un entier positif. Le graphique des résidus quadratiques est défini sur l'ensemble $ Z_{m} = \{\overline{0}, \overline{1}, \cdots, \overline{m-1}\}, $ où $ Z_{m} $ est l'anneau des classes de résidus de $ m $ , c'est-à-dire qu'il y a un bord entre $ \overline{x}, $ $ \overline{y}\in Z_{m} $ si et seulement si $ \overline{x}^{2}\equiv \overline{y}^{2}\ ; (\text{mod}\ ; m) $ . Nous caractérisons ces graphiques en termes de graphique complet pour certaines classes particulières de $ m $ .Translated Description (Spanish)
En matemáticas e informática, la partición de un conjunto en dos o más subconjuntos disjuntos de sumas iguales es un problema NP-completo bien conocido, también conocido como problema de partición. Hay varios enfoques para superar este problema para alguna elección particular de números enteros. Aquí, usamos un gráfico de residuos cuadráticos para determinar las posibles particiones de enteros positivos $ m = 2^{\beta}, q^{\beta}, 2^{\beta}q, $ $ 2q^{\beta}, qp, $ donde $ p $, $ q $ son números primos impares y $ \beta $ es cualquier entero positivo. El gráfico cuadrático de residuos se define en el conjunto $ Z_{m} = \{\overline{0}, \overline{1}, \cdots, \overline{m-1}\}, $ donde $ Z_{m} $ es el anillo de clases de residuos de $ m $, es decir, hay un borde entre $ \overline{x}, $ $ \overline{y}\en Z_{m} $ si y solo si $ \overline{x}^{2}\equiv \overline{y}^{2}\; (\text{mod}\; m) $. Caracterizamos estos gráficos en términos de gráfico completo para algunas clases particulares de $ m $.Additional details
Additional titles
- Translated title (Arabic)
- نهج جديد للعثور على أقسام $ Z _{ m }$ مع مجموعات فرعية متساوية المجموع عبر الرسوم البيانية الكاملة
- Translated title (French)
- Une nouvelle approche pour trouver des partitions de $ Z_{m} $ avec des sous-ensembles de somme égale via des graphiques complets
- Translated title (Spanish)
- Un enfoque novedoso para encontrar particiones de $ Z_{m} $ con subconjuntos de suma igual a través de gráficos completos
Identifiers
- Other
- https://openalex.org/W3178370611
- DOI
- 10.3934/math.2021581
References
- https://openalex.org/W1592261758
- https://openalex.org/W1986022934
- https://openalex.org/W2000009242
- https://openalex.org/W2016060847
- https://openalex.org/W2065529316
- https://openalex.org/W2137608611
- https://openalex.org/W2334273749
- https://openalex.org/W2522230967
- https://openalex.org/W2962910558
- https://openalex.org/W3000987653
- https://openalex.org/W3122433485
- https://openalex.org/W3130951907
- https://openalex.org/W3175400399