Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA optimization algorithm for determining the thickness of complete graphs and complete bipartite graphs
خوارزمية أمثلية لتحديد ثخانة البيان التام والثنائي التام
1815
1 17
0
(
0
)
Added by
Aِl-Baath University ورقة بحثية
Publication date
2014
fields
Informatics Engineering
and research's language is
العربية
Created by
Shamra Editor
Ask ChatGPT about the research
نرمز نظرياً لثخانة البيان G ب( Φ(G وتعرف ثخانة البيان بأنها العدد الأصغري من البيانات الجزئية المسطحة(المستوية ) والتي نستطيع الحصول عليها من تحميل البيان الأصلي G والبيان المسطح هو كل بيان يمكن إعادة رسمه في المستوي بدون أن تتقاطع أضلاعه (خطوط التوصيّل بين الر ؤوس)، لذلك عرفت مسألة تحديد ثخانة البيان كمسألة تنتمي إلى صف المسائل .NP-complete سنقدم في هذا البحث تطبيقاً لخوارزمية تجريبية Heuristic Algorithm تعتمد على مفهوم محاكاة تلدين الفلزات الأمثلScheme Simulated Annealing Optimization New- hick الذي يساعد في تحسين نتائج الخوارزمية التجريبية المقترحة حيث أعطى حلاً فعالاً وسريعاً في إيجاد ثخانة البيانات التامة والثنائية التامة عندما يكون عدد رؤوس البيان n<=30 وأبطأ عندما يكون أكبر من ذلك. أخيرا نعرض نتائج تطبيق هذه الخوارزمية على الخوارزمية التجريبية فنلاحظ بأنها أعطت حلاً أمثلياً لتحديد ثخانة البيانات التامة والثنائية التامة. كما تمّت برمجة هذه الخوارزمية باستخدام لغة عالية المستوى ++C بمفهوم غرضي التوجه وقد حصلنا على النتائج بتنفيذ البرنامج على حاسوب بمواصفات RAM 2GB, CPU, M350 2.27GHZ
The graph-theoretical thickness (shortly thickness)of graph G, denoted by Φ(G), is the minimum number of planar subgraphs into which the graph can be decomposed, and a graph that can be drawn in the plane without any of its edges intersecting is called a planar graph. determining the thickness of a given graph is known to be an NP-complete problem. In this paper we introduce an application heuristic algorithm for determining the thickness. Our algorithm is based on simulated annealing optimization scheme which provide the results of the New-thick (1). We show that the simulated annealing is a efficient method to obtain good approximation for the thickness when the number vertices are at most 30 otherwise it is slower. Finally, we apply this algorithm on the heuristic algorithm Newthick and we show that the algorithm produces a good approximation and optimization solution for the thickness, and we program this algorithm with C++, and running it by laptop has RAM 2GB and CPU 2.27GHZ.
Artificial intelligence review:
Research summary
تتناول هذه الورقة البحثية مسألة تحديد تخانة البيانات التامة والثنائية التامة، وهي مسألة تنتمي إلى صف المسائل NP-complete. تقدم الورقة خوارزمية تجريبية تعتمد على مفهوم محاكاة تلدين الفلزات الأمثل (Simulated Annealing Optimization) لتحسين نتائج الخوارزمية المقترحة New-thick. تُظهر النتائج أن الخوارزمية المقترحة فعالة وسريعة عندما يكون عدد رؤوس البيان أقل من أو يساوي 30، لكنها تصبح أبطأ عندما يزيد العدد عن ذلك. تم برمجة الخوارزمية باستخدام لغة ++C وتم تنفيذها على حاسوب بمواصفات RAM 2GB و CPU 2.27GHz. تُظهر النتائج أن الخوارزمية الجديدة تعطي حلاً أمثلياً لتحديد تخانة البيانات التامة والثنائية التامة مقارنة بالخوارزميات السابقة.
Critical review
دراسة نقدية: تقدم الورقة البحثية حلاً مبتكراً لمشكلة معقدة في نظرية البيانات، ولكن هناك بعض النقاط التي يمكن تحسينها. أولاً، على الرغم من أن الخوارزمية فعالة لرؤوس البيانات التي لا تتجاوز 30، إلا أنها تصبح أبطأ مع زيادة عدد الرؤوس، مما يحد من تطبيقها على البيانات الكبيرة. ثانياً، لم يتم تقديم تحليل تفصيلي لكيفية تأثير بارامترات التبريد والتجميد على أداء الخوارزمية، وهو أمر مهم لفهم كيفية تحسين الخوارزمية بشكل أكبر. أخيراً، قد يكون من المفيد تقديم مقارنة أكثر تفصيلاً مع خوارزميات أخرى مشابهة لتحديد مدى تفوق الخوارزمية المقترحة.
Questions related to the research
-
ما هي الخوارزمية المقترحة في هذه الورقة لتحديد تخانة البيانات التامة والثنائية التامة؟
الخوارزمية المقترحة هي New-thick، والتي تعتمد على مفهوم محاكاة تلدين الفلزات الأمثل لتحسين نتائج الخوارزمية التجريبية.
-
ما هي مشكلة تحديد تخانة البيانات ولماذا تعتبر معقدة؟
تحديد تخانة البيانات هو عملية تقسيم البيان إلى أقل عدد ممكن من البيانات الجزئية المسطحة. تعتبر هذه المشكلة معقدة لأنها تنتمي إلى صف المسائل NP-complete، مما يعني أنه لا يوجد حل بزمن كثيرة حدود معروف لها.
-
ما هي نتائج تطبيق الخوارزمية المقترحة على البيانات التامة والثنائية التامة؟
أظهرت النتائج أن الخوارزمية المقترحة تعطي حلاً أمثلياً لتحديد تخانة البيانات التامة والثنائية التامة عندما يكون عدد رؤوس البيان أقل من أو يساوي 30، لكنها تصبح أبطأ عندما يزيد العدد عن ذلك.
-
ما هي اللغة البرمجية المستخدمة في برمجة الخوارزمية وما هي مواصفات الحاسوب المستخدم لتنفيذها؟
تم برمجة الخوارزمية باستخدام لغة ++C وتم تنفيذها على حاسوب بمواصفات RAM 2GB و CPU 2.27GHz.
References used
BONDY, J and MURTY, U. S 2008-Graph Theory . Springer
artrand,G 1993-Applied and Algorithmic Graph Theory. McGraw-Hill,Inc, International Edition United States of America, 395
Daniel Liang,Y 2010-Introduction to Programming With C++. Pearson Education International, second edition United States of America, 694
Eles, P 2010- Simulated Annealing.Department of Computer and Information Science (IDA)Linköpings Universitet
JOHN,M. MICHAEL,J and JEFFRY,L 2008-Combinatorics and Graph Theory, second edition Springer, 392
rate research
Read More
The aim of this paper is to study and generalize some results that related by the complete continuity of the urysohn.s operator of two variables on a set on which a lebesgue meagure is defined and study uniform convergence sequence of the urysohn .s.
operators that defined by functions using convergence meager Depending on caratheodory condition of measurable sets .
In spite of the significant progress in surgery , the "best" surgical technique for
the management of complete rectal prolapse remains controversial, due to its low incidence, which is the
cause that there are no large prospective randomized trials
to attest to the superiority of one operation
over an other.
mentioned in the medical Purpose: To highlight the Sudeck's operation (1922), that is rarely literature;
and the modifications which I conducted on it. This operation is performed transabdominal and its
characterized by the fact that it reforms more than one pathological side of the rectal prolapse in adults;
with very encouraging results.
As it’s known, The Graph k-Colorability Problem (GCP) is a wellknown
NP-Hard Problem. This problem consists in finding the k
minimum number of colors to paint the vertices of a graph in such a way
that any two adjoined vertices, which are connecte
d by an edge, have
always different colors. In another words how can we color the edges of a
graph in such a way that any two edges joined by a vertex have always
different colors? In this paper we introduce a new effective algorithm for
coloring the edges of the graph. Our proposed algorithm enables us to
achieve a Continuously Edge Coloring (CEC) for a set of known graphs.
In this paper, we introduce an Effective algorithm to find the
shortest path in Multiple – Source Graph, by choosing the path
between the source and the distance that gives at least the length of
the path down to the sink. This algorithm is based
on the principle
of iteration to access the optimal solution of the shortest-path
problem, Where the algorithm steps are repeated for all the darts in
the Graph. We proved that the time of implementation of the
proposed algorithm in this paper is linear time O(n+L) and This is
considered the best times of the algorithms at all.
The all-nodes shortest paths problem is undoubtedly one of
the most basic problems in algorithmic graph theory. In this paper,
we introduce simple and efficient algorithm for all nodes shortest
paths problem for directed (undirected) graphs. In th
is problem, we
find the shortest path from a given source node to all other nodes in
the graph, in which the shortest path is a path with minimum cost,
i.e., sum of the edge weights.
We proved that the complexity of the proposed algorithm in
this paper depends only on the edges graph, and we show that the
time of implementation of this algorithm is linear time O(m) and
This is considered the best times of the algorithms at all. And
a Comparison between complexity of proposed algorithm and the
famous shortest path algorithms have been made, and the obtained
results have shown that the complexity of the proposed algorithm
is best.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
