Do you want to publish a course? Click here

A optimization algorithm for determining the thickness of complete graphs and complete bipartite graphs

خوارزمية أمثلية لتحديد ثخانة البيان التام والثنائي التام

1795   1   17   0 ( 0 )
 Publication date 2014
and research's language is العربية
 Created by Shamra Editor




Ask ChatGPT about the research

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
  1. ما هي الخوارزمية المقترحة في هذه الورقة لتحديد تخانة البيانات التامة والثنائية التامة؟

    الخوارزمية المقترحة هي New-thick، والتي تعتمد على مفهوم محاكاة تلدين الفلزات الأمثل لتحسين نتائج الخوارزمية التجريبية.

  2. ما هي مشكلة تحديد تخانة البيانات ولماذا تعتبر معقدة؟

    تحديد تخانة البيانات هو عملية تقسيم البيان إلى أقل عدد ممكن من البيانات الجزئية المسطحة. تعتبر هذه المشكلة معقدة لأنها تنتمي إلى صف المسائل NP-complete، مما يعني أنه لا يوجد حل بزمن كثيرة حدود معروف لها.

  3. ما هي نتائج تطبيق الخوارزمية المقترحة على البيانات التامة والثنائية التامة؟

    أظهرت النتائج أن الخوارزمية المقترحة تعطي حلاً أمثلياً لتحديد تخانة البيانات التامة والثنائية التامة عندما يكون عدد رؤوس البيان أقل من أو يساوي 30، لكنها تصبح أبطأ عندما يزيد العدد عن ذلك.

  4. ما هي اللغة البرمجية المستخدمة في برمجة الخوارزمية وما هي مواصفات الحاسوب المستخدم لتنفيذها؟

    تم برمجة الخوارزمية باستخدام لغة ++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

comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا