Zaloguj się

Gotowe bibliografie tematyczne / Edge coloring problem

Spis treści

Artykuły w czasopismach
Rozprawy doktorskie
Części książek
Streszczenia konferencji

Gotowa bibliografia na temat „Edge coloring problem”

Autor: Grafiati

Data publikacji: 6 września 2023

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Zobacz listy aktualnych artykułów, książek, rozpraw, streszczeń i innych źródeł naukowych na temat „Edge coloring problem”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Artykuły w czasopismach na temat "Edge coloring problem"

1

Li i Yu. "New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling". Algorithms 12, nr 7 (16.07.2019): 142. http://dx.doi.org/10.3390/a12070142.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

2

HUC, FLORIAN, CLÁUDIA LINHARES SALES i HERVÉ RIVANO. "THE PROPORTIONAL COLORING PROBLEM: OPTIMIZING BUFFERS IN RADIO MESH NETWORKS". Discrete Mathematics, Algorithms and Applications 04, nr 03 (6.08.2012): 1250028. http://dx.doi.org/10.1142/s1793830912500280.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

3

Hoppen, Carlos, i Hanno Lefmann. "Remarks on an Edge-coloring Problem". Electronic Notes in Theoretical Computer Science 346 (sierpień 2019): 511–21. http://dx.doi.org/10.1016/j.entcs.2019.08.045.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

4

Bourgeois, N., G. Lucarelli, I. Milis i V. Th Paschos. "Approximating the max-edge-coloring problem". Theoretical Computer Science 411, nr 34-36 (lipiec 2010): 3055–67. http://dx.doi.org/10.1016/j.tcs.2010.04.031.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

5

HUC, FLORIAN. "WEIGHTED-EDGE-COLORING OF k-DEGENERATE GRAPHS AND BIN-PACKING". Journal of Interconnection Networks 12, nr 01n02 (marzec 2011): 109–24. http://dx.doi.org/10.1142/s0219265911002861.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

6

Mertzios, George B., Hendrik Molter i Viktor Zamaraev. "Sliding Window Temporal Graph Coloring". Proceedings of the AAAI Conference on Artificial Intelligence 33 (17.07.2019): 7667–74. http://dx.doi.org/10.1609/aaai.v33i01.33017667.

Pełny tekst źródła

Streszczenie:

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).

Style APA, Harvard, Vancouver, ISO itp.

7

Larjomaa, Tommi, i Alexandru Popa. "The Min-Max Edge q-Coloring Problem". Journal of Graph Algorithms and Applications 19, nr 1 (2015): 507–28. http://dx.doi.org/10.7155/jgaa.00373.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

8

Lucarelli, Giorgio, Ioannis Milis i Vangelis T. Paschos. "On the max-weight edge coloring problem". Journal of Combinatorial Optimization 20, nr 4 (14.03.2009): 429–42. http://dx.doi.org/10.1007/s10878-009-9223-z.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

9

Faudree, R. J., Andr�as Gy�rf�s i R. H. Schelp. "An edge coloring problem for graph products". Journal of Graph Theory 23, nr 3 (listopad 1996): 297–302. http://dx.doi.org/10.1002/(sici)1097-0118(199611)23:3<297::aid-jgt9>3.0.co;2-n.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

10

TAMURA, HIROSHI, KAORU WATANABE, MASAKAZU SENGOKU i SHOJI SHINODA. "A CHANNEL ASSIGNMENT PROBLEM IN MULTIHOP WIRELESS NETWORKS AND GRAPH THEORY". Journal of Circuits, Systems and Computers 13, nr 02 (kwiecień 2004): 375–85. http://dx.doi.org/10.1142/s0218126604001398.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

Więcej źródeł

Rozprawy doktorskie na temat "Edge coloring problem"

1

Xie, Xuzhen, Takao Ono, Shin-ichi Nakao i Tomio Hirata. "NEARLY EQUITABLE EDGE-COLORING PROBLEM". INTELLIGENT MEDIA INTEGRATION NAGOYA UNIVERSITY / COE, 2006. http://hdl.handle.net/2237/10408.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

2

HIRATA, Tomio, i Takao ONO. "An Improved Algorithm for the Net Assignment Problem". Institute of Electronics, Information and Communication Engineers, 2001. http://hdl.handle.net/2237/15062.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

HIRATA, Tomio, Shin-ichi NAKANO, Takao ONO i 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

6

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

7

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

Pełny tekst źródła

Streszczenie:

碩士
東吳大學
資訊科學系
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.

Style APA, Harvard, Vancouver, ISO itp.

8

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

Pełny tekst źródła

Streszczenie:

碩士
國立交通大學
應用數學系所
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.

Style APA, Harvard, Vancouver, ISO itp.

9

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Części książek na temat "Edge coloring problem"

1

Lucarelli, Giorgio, Ioannis Milis i Vangelis Th Paschos. "On the Maximum Edge Coloring Problem". W Approximation and Online Algorithms, 279–92. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-540-93980-1_22.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

2

Bourgeois, Nicolas, Giorgio Lucarelli, Ioannis Milis i Vangelis Th Paschos. "Approximating the Max Edge-Coloring Problem". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

Mannino, Carlo, i A. Sassano. "Edge projection and the maximum cardinality stable set problem". W Cliques, Coloring, and Satisfiability, 205–19. Providence, Rhode Island: American Mathematical Society, 1996. http://dx.doi.org/10.1090/dimacs/026/11.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

4

Larjomaa, Tommi, i Alexandru Popa. "The Min-max Edge q-Coloring Problem". W Lecture Notes in Computer Science, 226–37. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-19315-1_20.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

5

Osawa, Hiroki, Akira Suzuki, Takehiro Ito i Xiao Zhou. "The Complexity of (List) Edge-Coloring Reconfiguration Problem". W WALCOM: Algorithms and Computation, 347–58. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-53925-6_27.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

6

Lucarelli, Giorgio, i Ioannis Milis. "Improved Approximation Algorithms for the Max-Edge Coloring Problem". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

7

Mincu, Radu Stefan, i Alexandru Popa. "Heuristic Algorithms for the Min-Max Edge 2-Coloring Problem". W Lecture Notes in Computer Science, 662–74. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94776-1_55.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

8

Matsui, Yasuko, i Tomomi Matsui. "Enumeration algorithm for the edge coloring problem on bipartite graphs". W Combinatorics and Computer Science, 18–26. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/3-540-61576-8_69.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

9

Goyal, Prachi, Vikram Kamat i Neeldhara Misra. "On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

10

Adamaszek, Anna, i Alexandru Popa. "Approximation and Hardness Results for the Maximum Edge q-coloring Problem". W Algorithms and Computation, 132–43. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-17514-5_12.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Streszczenia konferencji na temat "Edge coloring problem"

1

Jianu, Radu, Adrian Rusu, Andrew J. Fabian i David H. Laidlaw. "A Coloring Solution to the Edge Crossing Problem". W 2009 13th International Conference Information Visualisation, IV. IEEE, 2009. http://dx.doi.org/10.1109/iv.2009.66.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

2

Sobral, Gabriel A. G., Marina Groshaus i André L. P. Guedes. "Biclique edge-choosability in some classes of graphs∗". W II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3203.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

3

Hebrard, Emmanuel, i George Katsirelos. "Clause Learning and New Bounds for Graph Coloring". W 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.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

4

Mishkhal, Israa, Sarah Abd AL Kareem, Hassan Hadi Saleh, Ammar Alqayyar, Iman Hussein i Israa Asaad Jassim. "Solving Course Timetabling Problem Based on the Edge Coloring Methodology by Using Jedite". W 2019 1st AL-Noor International Conference for Science and Technology (NICST). IEEE, 2019. http://dx.doi.org/10.1109/nicst49484.2019.9043794.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

5

Hidzir, Nurhafizahtulhusna Binti, i Syarifah Zyurina Binti Nordin. "Vertex and edge coloring method for timetabling problem in minimizing the time frame". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

6

Bossek, Jakob, i Dirk Sudholt. "Time complexity analysis of RLS and (1 + 1) EA for the edge coloring problem". W the 15th ACM/SIGEVO Conference. New York, New York, USA: ACM Press, 2019. http://dx.doi.org/10.1145/3299904.3340311.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

7

Garvardt, Jaroslav, Niels Grüttemeier, Christian Komusiewicz i Nils Morawietz. "Parameterized Local Search for Max c-Cut". W 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.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

8

Rocha, Aleffer, Sheila M. Almeida i Leandro M. Zatesko. "The Rainbow Connection Number of Triangular Snake Graphs". W Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/etc.2020.11091.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

9

Botler, Fábio, Lucas Colucci, Paulo Matias, Guilherme Mota, Roberto Parente i Matheus Secco. "Proper edge colorings of complete graphs without repeated triangles". W Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.222917.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

10

Cavalar, Bruno Pasqualotto. "Ramsey-type problems in orientations of graphs ⇤". W III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3172.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!