Relevant bibliographies by topics / Edge coloring problem

Academic literature on the topic 'Edge coloring problem'

Author: Grafiati
Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Edge coloring problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Edge coloring problem"

1

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.

Full text
Abstract:
For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph problems, including the “maximum edge coloring problem”, the “maximum degree edge coloring problem”, and the “cost-sharing maximum edge coloring problem” to formulate these kinds of distribution problems. Next, we propose an approximation algorithm with a ratio bound of two for the maximum edge coloring problem when the input graph is biplanar. Moreover, we also prove that the “cost-sharing maximum edge coloring problem” is an NP-complete problem even when the input graph is biplanar.
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
Abstract:
In this paper, we consider a new edge coloring problem to model call scheduling optimization issues in wireless mesh networks: the proportional coloring. It consists in finding a minimum cost edge coloring of a graph which preserves the proportion given by the weights associated to each of its edges. We show that deciding if a weighted graph admits a proportional coloring is pseudo-polynomial while determining its proportional chromatic index is NP-hard. We then give lower and upper bounds for this parameter that can be computed in pseudo-polynomial time. We finally identify a class of graphs and a class of weighted graphs for which the proportional chromatic index can be exactly determined.
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
Abstract:
The weighted-edge-coloring problem of an edge-weighted graph whose weights are between 0 and 1, consists in finding a coloring using as few colors as possible and satisfying the following constraints: the sum of weights of edges with the same color and incident to the same vertex must be at most 1. In 1991, Chung and Ross conjectured that if G is bipartite, then [Formula: see text] colors are always sufficient to weighted-edge-color (G,w), where [Formula: see text] is the maximum of the sums of the weights of the edges incident to a vertex. We prove this is true for edge-weighted graphs with multiple edges whose underlying graph is a tree. We further generalise this conjecture to non-bipartite graphs and prove the generalised conjecture for simple edge-weighted outerplanar graphs. Finally, we introduce a list version of this coloring together with the list-bin-packing problem, which allows us to obtain new results concerning the original coloring for a specific class of graphs, namely the k-weight-degenerate weighted graph.
APA, Harvard, Vancouver, ISO, and other styles
6

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.

Full text
Abstract:
Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in stark contrast to practice where data is inherently dynamic and subject to discrete changes over time. A temporal graph is a graph whose edges are assigned a set of integer time labels, indicating at which discrete time steps the edge is active. In this paper we present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and a natural number ∆, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of ∆ consecutive time steps, in which an edge is active, this edge is properly colored (i.e. its endpoints are assigned two different colors) at least once during that time window, and (ii) the total number of different colors is minimized. This sliding window temporal coloring problem abstractly captures many realistic graph coloring scenarios in which the underlying network changes over time, such as dynamically assigning communication channels to moving agents. We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear-time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH).
APA, Harvard, Vancouver, ISO, and other styles
7

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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.

Full text
Abstract:
Multihop wireless networks consist of mobile terminals with personal communication devices. Each terminal can receive a message and then send it to another terminal. In these networks, it is important to assign channels for communications to each terminal efficiently. There are some studies on this assignment problem using a conventional edge coloring in graph theory. In this paper, we propose a new edge coloring problem in graph and network theory on this assignment problem and we discuss the computational complexity of the problem. This edge coloring problem takes the degree of interference into consideration. Therefore, we can reuse the channels more efficiently compared with the conventional method.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Edge coloring problem"

1

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
Abstract:
Submitted by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:41Z 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: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.
APA, Harvard, Vancouver, ISO, and other styles
6

Valicov, Petru. "Problèmes de placement, de coloration et d’identification." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14549/document.

Full text
Abstract:
Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits
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
APA, Harvard, Vancouver, ISO, and other styles
7

Liao, Yi-Xiang, and 廖翌翔. "Resolving Vehicle Routing Problem for Reverse Logistics using Edge Coloring." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/10614347090410814864.

Full text
Abstract:
碩士
東吳大學
資訊科學系
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.
APA, Harvard, Vancouver, ISO, and other styles
8

Chen, Hung-Shiun, and 陳泓勳. "Decidability Problems of Triangle Edge-coloring." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/60033521582725706434.

Full text
Abstract:
碩士
國立交通大學
應用數學系所
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.
APA, Harvard, Vancouver, ISO, and other styles
9

Lai, De-Jan, and 賴德展. "Decidability Problems of Hexagonal Edge-coloring with Two Colors." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/55669493853428608242.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Edge coloring problem"

1

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Edge coloring problem"

1

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
Abstract:
In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K3free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K3-free and chordal bipartite graphs for any given 2-list assignment to edges.
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
Abstract:
Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov’s tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in a branch- and-bound search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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.

Full text
Abstract:
In the NP-hard Max c-Cut problem, one is given an undirected edge-weighted graph G and wants to color the vertices of G with c colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with c=2 is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS-Max c-Cut where we are additionally given a vertex coloring f and an integer k and the task is to find a better coloring f' that differs from f in at most k entries, if such a coloring exists; otherwise, f is k-optimal. We show that LS-Max c-Cut presumably cannot be solved in g(k) · nᴼ⁽¹⁾ time even on bipartite graphs, for all c ≥ 2. We then show an algorithm for LS-Max c-Cut with running time O((3eΔ)ᵏ · c · k³ · Δ · n), where Δ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for state-of-the-art heuristics for Max c-Cut. We show that using parameterized local search, the results of this heuristic can be further improved on a set of standard benchmark instances.
APA, Harvard, Vancouver, ISO, and other styles
8

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.

Full text
Abstract:
Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention last years in Combinatorics. The rainbow connection number of a graph G is the least number of colors for a (not necessarily proper) edge coloring of G such that between any pair of vertices there is a path whose edge colors are all distinct. In this paper we determine the rainbow connection number of the triple triangular snake graphs.
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
Abstract:
In this paper, we consider the problem of computing the minimum number of colors needed to properly color the edges of a complete graph on $n$ vertices so that there are no pair of vertex-disjoint triangles colored with the same colors. This problem was introduced recently (in a more general context) by Conlon and Tyomkyn, and the corresponding value was known for odd $n$. We compute this number for another infinite set of values of $n$, and discuss some small cases.
APA, Harvard, Vancouver, ISO, and other styles
10

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.

Full text
Abstract:
The Ramsey number R(H) of a graph H is the minimum number n such that there exists a graph G on n vertices with the property that every two-coloring of its edges contains a monochromatic copy of H. In this work we study a variant of this notion, called the oriented Ramsey problem, for an acyclic oriented graph H~ , in which we require that every orientation G~ of the graph G contains a copy of H~ . We also study the threshold function for this problem in random graphs. Finally, we consider the isometric case, in which we require the copy to be isometric, by which we mean that, for every two vertices x, y 2 V (H~ ) and their respective copies x0, y0 in G~ , the distance between x and y is equal to the distance between x0 and y0.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Edge coloring problem' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography