فهرست مقالات Graph coloring

• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  1 - بررسی بیشینه تعداد رده های احاطه گر در رنگ آمیزی یک گراف
  مرتضی فغانی
  در این مقاله، عدد رنگی χ-احاطه گر، یعنی d_χ (G) در یک گراف G مورد بررسی قرار می گیرد. این عدد برابر است با ماکزیمم تعداد رده های رنگی که احاطه گر (یا تسلطی) بوده و G توسط χ(G) رنگ، رنگ آمیزی می شود. همچنین، نشان خواهیم داد که d_χ (G∨H)=d_χ (G)+d_& چکیده کامل

  در این مقاله، عدد رنگی χ-احاطه گر، یعنی d_χ (G) در یک گراف G مورد بررسی قرار می گیرد. این عدد برابر است با ماکزیمم تعداد رده های رنگی که احاطه گر (یا تسلطی) بوده و G توسط χ(G) رنگ، رنگ آمیزی می شود. همچنین، نشان خواهیم داد که d_χ (G∨H)=d_χ (G)+d_χ (H) است بطوریکه G∨H به معنای الحاق G و H است. نتیجه فوق به ما کمک می کند که رده های گراف هایی که d_χ (G)>1 و d_χ (G)=χ(G) است را مشخص نماییم. همچنین در این مقاله، برخی نتایج در ارتباط با عدد رنگی χ-احاطه گر یک گراف ارائه می شود که مرتبط با سوالات مطرح شده در برخی مقالات اخیر حول مشخص سازی گراف های همبند G براساس مقدار d_χ (G) می باشد. در بخش پایانی مقاله، براساس قضایای حاصل این پرسش را مطرح می کنیم که آیا گراف های بدون مثلث G با شرط d_χ (G )=χ(G)=k موجود است؟آیا G دارای یک زیرگراف k-رنگ پذیر یکتا است یا خیر؟ بعلاوه، آیا یافتن چنین گراف هایی از کمر به اندازه کافی بزرگ میسر می باشد؟ پرونده مقاله
• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  2 - Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm
  Javad Behnamian
  10.22094/joie.2017.599.1385
  This paper considers a different version of the parallel machines scheduling problem in which the parallel jobs simultaneously requirea pre-specifiedjob-dependent number of machines when being processed.This relaxation departs from one of the classic scheduling assumpti چکیده کامل

  This paper considers a different version of the parallel machines scheduling problem in which the parallel jobs simultaneously requirea pre-specifiedjob-dependent number of machines when being processed.This relaxation departs from one of the classic scheduling assumptions. While the analytical conditions can be easily statedfor some simple models, a graph model approach is required when conflicts of processor usage are present. The main decisions and solving steps are as follows, respectively. (i) Converting the scheduling problem to graph model; (ii) Dividing jobs into independent sets: in this phase, we propose a semi-definite relaxation algorithm in which we use graph coloring concept; (iii) Sequencing the independent sets as a single-machine scheduling in which jobs in such a system arejob sets formed by using a semi-definite relaxation solution and determining the problem as a schedule that minimizes the sum of the tardiness of jobs. In this regard, after grouping the jobs by a semi-definite programming relaxation algorithm, we used the rounding algorithm for graph coloring. We also proposed a variable neighborhood search algorithm for sequencing the obtained job sets in order to minimize the sum of the tardiness. Experimental results show that this methodology is interesting by obtaining good results. پرونده مقاله
• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  3 - A new method for solving of the Graph Coloring Problem based on a fuzzy logic and whale optimization algorithm
  طاها مصطفایی فرزین مدرس خیابانی نیما جعفری نویمی پور بهروز دانشیان
  Abstract: In recent years, Graph Coloring Problem (GCP) is one of the main optimization problems from literature. Many real world problems interacting with changing environments can be modeled by dynamic graphs. Graph vertex coloring with a given number of colors is a w چکیده کامل

  Abstract: In recent years, Graph Coloring Problem (GCP) is one of the main optimization problems from literature. Many real world problems interacting with changing environments can be modeled by dynamic graphs. Graph vertex coloring with a given number of colors is a well-known and much-studied NP-hard problem. Meta-heuristic algorithms are a good choice to solve GCP because they are suitable for problems with NP-hard complexity. However, in many previously proposed algorithms, there are common problems such as runtime algorithm and low convergence of algorithm. Therefore, in this paper, we propose the Fuzzy Whale Optimization Algorithm (FWOA), a variety of basic Whale Optimization Algorithm (WOA), to improve runtime and convergence of algorithm in the GCP. Since WOA at first was introduced for solving continuous problem, we need a discrete WOA. Hence, to use FWOA to discrete search space, the standard arithmetic operators such as addition, subtraction and multiplication extant in FWOA encircling prey, exploitation phase and exploration phase operators based on distance’s theory needs to be redefined in the discrete space. Parameters p and r, are defined randomly in the WOA algorithm in FWOA algorithm defined as fuzzy and are selected in fuzzy tragedy. A set of graph coloring benchmark problems are solved and their performance are compared with some well-known heuristic search methods. Results illustrate that FWOA algorithm are the original focus of this work and in most cases success rate is nearly 100% and the runtime and convergence algorithm has been improved on some graphs. But as we have illustrated that comparison with other manners, we cannot deduce that our algorithm is the best in all instance of graphs. It can be said that a proposed algorithm is able to compete with other algorithms in this context. Obtained results approved the high performance of proposed method. پرونده مقاله
• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  4 - A new Simulated Annealing algorithm for the robust coloring problem
  M.A Gutiérrez-Andrade P Lara-Velázquez S.G de-los-Cobos-Silva
  The Robust Coloring Problem (RCP) is a generalization of the well-known Graph Coloring Problem where we seek for a solution that remains valid when extra edges are added. The RCP is used in scheduling of events with possible last-minute changes and study frequency assig چکیده کامل

  The Robust Coloring Problem (RCP) is a generalization of the well-known Graph Coloring Problem where we seek for a solution that remains valid when extra edges are added. The RCP is used in scheduling of events with possible last-minute changes and study frequency assignments of the electromagnetic spectrum. This problem has been proved as NP-hard and in instances larger than 30 vertices, meta-heuristics are required. In this paper a Simulated Annealing Algorithm is proposed, and his performance is compared against other tech-niques such as GRASP, Tabu Search and Scatter Search. In the classic instances of the problem our proposal method which gives the best solutions at this moment. پرونده مقاله