Добірка наукової літератури з теми "Edge coloring problem"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Edge coloring problem".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Edge coloring problem"
Li and Yu. "New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling." Algorithms 12, no. 7 (July 16, 2019): 142. http://dx.doi.org/10.3390/a12070142.
Повний текст джерелаHUC, FLORIAN, CLÁUDIA LINHARES SALES, and HERVÉ RIVANO. "THE PROPORTIONAL COLORING PROBLEM: OPTIMIZING BUFFERS IN RADIO MESH NETWORKS." Discrete Mathematics, Algorithms and Applications 04, no. 03 (August 6, 2012): 1250028. http://dx.doi.org/10.1142/s1793830912500280.
Повний текст джерелаHoppen, Carlos, and Hanno Lefmann. "Remarks on an Edge-coloring Problem." Electronic Notes in Theoretical Computer Science 346 (August 2019): 511–21. http://dx.doi.org/10.1016/j.entcs.2019.08.045.
Повний текст джерелаBourgeois, N., G. Lucarelli, I. Milis, and V. Th Paschos. "Approximating the max-edge-coloring problem." Theoretical Computer Science 411, no. 34-36 (July 2010): 3055–67. http://dx.doi.org/10.1016/j.tcs.2010.04.031.
Повний текст джерелаHUC, FLORIAN. "WEIGHTED-EDGE-COLORING OF k-DEGENERATE GRAPHS AND BIN-PACKING." Journal of Interconnection Networks 12, no. 01n02 (March 2011): 109–24. http://dx.doi.org/10.1142/s0219265911002861.
Повний текст джерелаMertzios, George B., Hendrik Molter, and Viktor Zamaraev. "Sliding Window Temporal Graph Coloring." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7667–74. http://dx.doi.org/10.1609/aaai.v33i01.33017667.
Повний текст джерелаLarjomaa, Tommi, and Alexandru Popa. "The Min-Max Edge q-Coloring Problem." Journal of Graph Algorithms and Applications 19, no. 1 (2015): 507–28. http://dx.doi.org/10.7155/jgaa.00373.
Повний текст джерелаLucarelli, Giorgio, Ioannis Milis, and Vangelis T. Paschos. "On the max-weight edge coloring problem." Journal of Combinatorial Optimization 20, no. 4 (March 14, 2009): 429–42. http://dx.doi.org/10.1007/s10878-009-9223-z.
Повний текст джерелаFaudree, R. J., Andr�as Gy�rf�s, and R. H. Schelp. "An edge coloring problem for graph products." Journal of Graph Theory 23, no. 3 (November 1996): 297–302. http://dx.doi.org/10.1002/(sici)1097-0118(199611)23:3<297::aid-jgt9>3.0.co;2-n.
Повний текст джерелаTAMURA, HIROSHI, KAORU WATANABE, MASAKAZU SENGOKU, and SHOJI SHINODA. "A CHANNEL ASSIGNMENT PROBLEM IN MULTIHOP WIRELESS NETWORKS AND GRAPH THEORY." Journal of Circuits, Systems and Computers 13, no. 02 (April 2004): 375–85. http://dx.doi.org/10.1142/s0218126604001398.
Повний текст джерелаДисертації з теми "Edge coloring problem"
Xie, Xuzhen, Takao Ono, Shin-ichi Nakao, and Tomio Hirata. "NEARLY EQUITABLE EDGE-COLORING PROBLEM." INTELLIGENT MEDIA INTEGRATION NAGOYA UNIVERSITY / COE, 2006. http://hdl.handle.net/2237/10408.
Повний текст джерелаHIRATA, Tomio, and Takao ONO. "An Improved Algorithm for the Net Assignment Problem." Institute of Electronics, Information and Communication Engineers, 2001. http://hdl.handle.net/2237/15062.
Повний текст джерелаHIRATA, Tomio, Shin-ichi NAKANO, Takao ONO, and Xuzhen XIE. "An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem." Institute of Electronics, Information and Communication Engineers, 2004. http://hdl.handle.net/2237/15064.
Повний текст джерелаCasselgren, Carl Johan. "On some graph coloring problems." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-43389.
Повний текст джерелаCruz, Jadder Bismarck de Sousa. "Coloração de Arestas em Grafos Split-Comparabilidade." Universidade Federal de São Carlos, 2017. https://repositorio.ufscar.br/handle/ufscar/9140.
Повний текст джерелаApproved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:55Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5)
Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:27:03Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5)
Made available in DSpace on 2017-10-09T16:27:11Z (GMT). No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) Previous issue date: 2017-05-02
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Let G = (V, E) be a simple and undirected graph. An edge-coloring is an assignment of colors to the edges of the graph such that any two adjacent edges receive different colors. The chromatic index of a graph G is the smallest number of colors such that G has an edge-coloring. Clearly, a lower bound for the chromatic index is the degree of the vertex of higher degree, denoted by ?(G). In 1964, Vizing proved that chromatic index is ?(G) or ?(G) + 1. The Classification Problem is to determine if the chromatic index is ?(G) (Class 1 ) or if it is ?(G) + 1 (Class 2 ). Let n be number of vertices of a graph G and let m be its number of edges. We say G is overfull if m > (n-1) 2 ?(G). Every overfull graph is Class 2. A graph is subgraph-overfull if it has a subgraph with same maximum degree and it is overfull. It is well-known that every overfull and subgraph-overfull graph is Class 2. The Overfull Conjecture asserts that every graph with ?(G) > n 3 is Class 2 if and only if it is subgraph-overfull. In this work we prove the Overfull Conjecture to a particular class of graphs, known as split-comparability graphs. The Overfull Conjecture was open to this class.
Dado um grafo simples e não direcionado G = (V, E), uma coloração de arestas é uma função que atribui cores às arestas do grafo tal que todas as arestas que incidem em um mesmo vértice têm cores distintas. O índice cromático é o número mínimo de cores para obter uma coloração própria das arestas de um grafo. Um limite inferior para o índice cromático é, claramente, o grau do vértice de maior grau, denotado por ?(G). Em 1964, Vizing provou que o índice cromático ou é ?(G) ou ?(G) + 1, surgindo assim o Problema da Classificação, que consiste em determinar se o índice cromático é ?(G) (Classe 1 ) ou ?(G) + 1 (Classe 2 ). Seja n o número de vértices de um grafo G e m seu número de arestas. Dizemos que um grafo é sobrecarregado se m > (n-1) 2 ?(G). Um grafo é subgrafo-sobrecarregado se tem um subgrafo de mesmo grau máximo que é sobrecarregado. É sabido que se um grafo é sobrecarregado ou subgrafo-sobrecarregado ele é necessariamente Classe 2. A Conjectura Overfull é uma famosa conjectura de coloração de arestas e diz que um grafo com ?(G) > n 3 é Classe 2 se e somente se é subgrafo-sobrecarregado. Neste trabalho provamos a Conjectura Overfull para uma classe de grafos, a classe dos grafos split-comparabilidade. Até este momento a Conjectura Overfull estava aberta para esta classe.
Valicov, Petru. "Problèmes de placement, de coloration et d’identification." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14549/document.
Повний текст джерелаIn this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs
Liao, Yi-Xiang, and 廖翌翔. "Resolving Vehicle Routing Problem for Reverse Logistics using Edge Coloring." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/10614347090410814864.
Повний текст джерела東吳大學
資訊科學系
96
The vehicle routing problem with time windows constraints belongs to an optimization problem with a constraint assembly of large scale, nonlinear and mixed-integer, and while the problem scale is becoming larger, the operating time needed for a solution is becoming longer as well, or even there is probably no way to obtain the optimum solution. Currently, the vehicle routing problems mostly focus on the field of forward logistics, not much on the studies of reverse logistics. Therefore, the present study presents an Iterative Heuristic Algorithm combined with coloring theory and minimum cost algorithm strategy, utilizing the concept of vertex coloring in the coloring theory and link defining constraints in the route planning so as to construct a route map graph, meanwhile, performing a coloring ocess on this graph along with to the Minimum Cost Algorithm in order to compute a service route of minimum total cost containing the original travel cost plus a penalty cost which was generated due to the violation oftime windows, so that it can be used as an important basis for planning the vehicle routing in reverse logistics, and in addition, utilizing the Iterative Algorithm Method to improve the solution quality and efficiency.
Chen, Hung-Shiun, and 陳泓勳. "Decidability Problems of Triangle Edge-coloring." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/60033521582725706434.
Повний текст джерела國立交通大學
應用數學系所
98
This investigation is about tiling the whole plane with upper triangles and lower triangles which have colors on edges. Upper and lower triangles can be placed side by side if each of the intersections has the same color. In this paper, we consider upper and lower triangle with two and three colors on edges. The problem we studied is that: any set of triangle that can fill with the whole plane whether it can cover the whole plane periodically. We use an algorithm to do the problem and get the result by computers. Finally, the main result of this paper is that the whole plane can be tiling by triangle with two and three colors if and only if the whole plane is covered by the local pattern periodically.
Lai, De-Jan, and 賴德展. "Decidability Problems of Hexagonal Edge-coloring with Two Colors." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/55669493853428608242.
Повний текст джерелаЧастини книг з теми "Edge coloring problem"
Lucarelli, Giorgio, Ioannis Milis, and Vangelis Th Paschos. "On the Maximum Edge Coloring Problem." In Approximation and Online Algorithms, 279–92. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-540-93980-1_22.
Повний текст джерелаBourgeois, Nicolas, Giorgio Lucarelli, Ioannis Milis, and Vangelis Th Paschos. "Approximating the Max Edge-Coloring Problem." In Lecture Notes in Computer Science, 83–94. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-10217-2_11.
Повний текст джерелаMannino, Carlo, and A. Sassano. "Edge projection and the maximum cardinality stable set problem." In Cliques, Coloring, and Satisfiability, 205–19. Providence, Rhode Island: American Mathematical Society, 1996. http://dx.doi.org/10.1090/dimacs/026/11.
Повний текст джерелаLarjomaa, Tommi, and Alexandru Popa. "The Min-max Edge q-Coloring Problem." In Lecture Notes in Computer Science, 226–37. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-19315-1_20.
Повний текст джерелаOsawa, Hiroki, Akira Suzuki, Takehiro Ito, and Xiao Zhou. "The Complexity of (List) Edge-Coloring Reconfiguration Problem." In WALCOM: Algorithms and Computation, 347–58. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-53925-6_27.
Повний текст джерелаLucarelli, Giorgio, and Ioannis Milis. "Improved Approximation Algorithms for the Max-Edge Coloring Problem." In Theory and Practice of Algorithms in (Computer) Systems, 206–16. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-19754-3_21.
Повний текст джерелаMincu, Radu Stefan, and Alexandru Popa. "Heuristic Algorithms for the Min-Max Edge 2-Coloring Problem." In Lecture Notes in Computer Science, 662–74. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94776-1_55.
Повний текст джерелаMatsui, Yasuko, and Tomomi Matsui. "Enumeration algorithm for the edge coloring problem on bipartite graphs." In Combinatorics and Computer Science, 18–26. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/3-540-61576-8_69.
Повний текст джерелаGoyal, Prachi, Vikram Kamat, and Neeldhara Misra. "On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem." In Mathematical Foundations of Computer Science 2013, 492–503. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40313-2_44.
Повний текст джерелаAdamaszek, Anna, and Alexandru Popa. "Approximation and Hardness Results for the Maximum Edge q-coloring Problem." In Algorithms and Computation, 132–43. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-17514-5_12.
Повний текст джерелаТези доповідей конференцій з теми "Edge coloring problem"
Jianu, Radu, Adrian Rusu, Andrew J. Fabian, and David H. Laidlaw. "A Coloring Solution to the Edge Crossing Problem." In 2009 13th International Conference Information Visualisation, IV. IEEE, 2009. http://dx.doi.org/10.1109/iv.2009.66.
Повний текст джерелаSobral, Gabriel A. G., Marina Groshaus, and André L. P. Guedes. "Biclique edge-choosability in some classes of graphs∗." In II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3203.
Повний текст джерелаHebrard, Emmanuel, and George Katsirelos. "Clause Learning and New Bounds for Graph Coloring." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/856.
Повний текст джерелаMishkhal, Israa, Sarah Abd AL Kareem, Hassan Hadi Saleh, Ammar Alqayyar, Iman Hussein, and Israa Asaad Jassim. "Solving Course Timetabling Problem Based on the Edge Coloring Methodology by Using Jedite." In 2019 1st AL-Noor International Conference for Science and Technology (NICST). IEEE, 2019. http://dx.doi.org/10.1109/nicst49484.2019.9043794.
Повний текст джерелаHidzir, Nurhafizahtulhusna Binti, and Syarifah Zyurina Binti Nordin. "Vertex and edge coloring method for timetabling problem in minimizing the time frame." In PROCEEDING OF THE 25TH NATIONAL SYMPOSIUM ON MATHEMATICAL SCIENCES (SKSM25): Mathematical Sciences as the Core of Intellectual Excellence. Author(s), 2018. http://dx.doi.org/10.1063/1.5041605.
Повний текст джерелаBossek, Jakob, and Dirk Sudholt. "Time complexity analysis of RLS and (1 + 1) EA for the edge coloring problem." In the 15th ACM/SIGEVO Conference. New York, New York, USA: ACM Press, 2019. http://dx.doi.org/10.1145/3299904.3340311.
Повний текст джерелаGarvardt, Jaroslav, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. "Parameterized Local Search for Max c-Cut." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/620.
Повний текст джерелаRocha, Aleffer, Sheila M. Almeida, and Leandro M. Zatesko. "The Rainbow Connection Number of Triangular Snake Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/etc.2020.11091.
Повний текст джерелаBotler, Fábio, Lucas Colucci, Paulo Matias, Guilherme Mota, Roberto Parente, and Matheus Secco. "Proper edge colorings of complete graphs without repeated triangles." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.222917.
Повний текст джерелаCavalar, Bruno Pasqualotto. "Ramsey-type problems in orientations of graphs ⇤." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3172.
Повний текст джерела