Acceder

Bibliografías temáticas / Edge coloring problem / Artículos de revistas

Artículos de revistas sobre el tema "Edge coloring problem"

Siga este enlace para ver otros tipos de publicaciones sobre el tema: Edge coloring problem.

Autor: Grafiati

Publicado: 6 de septiembre de 2023

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte los 50 mejores artículos de revistas para su investigación sobre el tema "Edge coloring problem".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Explore artículos de revistas sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.

1

Li y Yu. "New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling". Algorithms 12, n.º 7 (16 de julio de 2019): 142. http://dx.doi.org/10.3390/a12070142.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

6

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

Imreh, Csanád y Judit Nagy-György. "Online hypergraph coloring with rejection". Acta Universitatis Sapientiae, Informatica 7, n.º 1 (1 de junio de 2015): 5–17. http://dx.doi.org/10.1515/ausi-2015-0009.

Texto completo

Resumen

Abstract In this paper we investigate the online hypergraph coloring problem with rejection, where the algorithm is allowed to reject a vertex instead of coloring it but each vertex has a penalty which has to be paid if it is not colored. The goal is to minimize the sum of the number of the used colors for the accepted vertices and the total penalty paid for the rejected ones. We study the online problem which means that the algorithm receives the vertices of the hypergraph in some order v1, . . . , vn and it must decide about vi by only looking at the subhypergraph Hi = (Vi, Ei) where Vi = {v1, . . . , vi} and Ei contains the edges of the hypergraph which are subsets of Vi. We consider two models: in the full edge model only the edges where each vertex is accepted must be well-colored, in the trace model the subsets of the edges formed by the accepted vertices must be well colored as well. We consider proper and conflict free colorings. We present in each cases optimal online algorithms in the sense that they achieve asymptotically the smallest possible competitive ratio.

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

Jin, Zemin, Kun Ye, He Chen y Yuefang Sun. "Large rainbow matchings in semi-strong edge-colorings of graphs". Discrete Mathematics, Algorithms and Applications 10, n.º 02 (abril de 2018): 1850021. http://dx.doi.org/10.1142/s1793830918500210.

Texto completo

Resumen

The lower bounds for the size of maximum rainbow matching in properly edge-colored graphs have been studied deeply during the last decades. An edge-coloring of a graph [Formula: see text] is called a strong edge-coloring if each path of length at most three is rainbow. Clearly, the strong edge-coloring is a natural generalization of the proper one. Recently, Babu et al. considered the problem in the strongly edge-colored graphs. In this paper, we introduce a semi-strong edge-coloring of graphs and consider the existence of large rainbow matchings in it.

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

SKULRATTANAKULCHAI, SAN y HAROLD N. GABOW. "COLORING ALGORITHMS ON SUBCUBIC GRAPHS". International Journal of Foundations of Computer Science 15, n.º 01 (febrero de 2004): 21–40. http://dx.doi.org/10.1142/s0129054104002285.

Texto completo

Resumen

We present efficient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The first algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears to be simpler than previous ones. The second algorithm is the first randomized EREW PRAM algorithm for the same problem. It uses O(n/ log n) processors and runs in O( log n) time with high probability, where n is the number of vertices of the graph. The third algorithm is the first linear-time algorithm to 5-total-color subcubic graphs. The fourth algorithm generalizes this to get the first linear-time algorithm to 5-list-total-color subcubic graphs. Our sequential algorithms are based on a method of ordering the vertices and edges by traversing a spanning tree of a graph in a bottom-up fashion. Our parallel algorithm is based on a simple decomposition principle for subcubic graphs.

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

Zhou, Yangyang, Dongyang Zhao, Mingyuan Ma y Jin Xu. "Domination Coloring of Graphs". Mathematics 10, n.º 6 (21 de marzo de 2022): 998. http://dx.doi.org/10.3390/math10060998.

Texto completo

Resumen

A domination coloring of a graph G is a proper vertex coloring of G, such that each vertex of G dominates at least one color class (possibly its own class), and each color class is dominated by at least one vertex. The minimum number of colors among all domination colorings is called the domination chromatic number, denoted by χdd(G). In this paper, we study the complexity of the k-domination coloring problem by proving its NP-completeness for arbitrary graphs. We give basic results and properties of χdd(G), including the bounds and characterization results, and further research χdd(G) of some special classes of graphs, such as the split graphs, the generalized Petersen graphs, corona products, and edge corona products. Several results on graphs with χdd(G)=χ(G) are presented. Moreover, an application of domination colorings in social networks is proposed.

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

Zhong, Chuang y Shuangliang Tian. "Neighbor Sum Distinguishing Edge (Total) Coloring of Generalized Corona Product". Journal of Physics: Conference Series 2381, n.º 1 (1 de diciembre de 2022): 012031. http://dx.doi.org/10.1088/1742-6596/2381/1/012031.

Texto completo

Resumen

Abstract The coloring theory of graphs is an important part of graph theory research. The key problem of the coloring theory of graphs is to determine the coloring number of each kind of coloring. Traditional coloring concepts mainly include proper vertex coloring, proper edge coloring, proper total coloring, and so on. In recent years, scholars at home and abroad have put forward some new coloring concepts, such as neighbor vertex distinguishing edge (total) coloring, and neighbor sum distinguishing edge (total) coloring, based on traditional coloring concepts and by adding other constraints. Some valuable results have been obtained, which further enrich the theory of graph coloring. For a proper [k]-edge coloring of a graph G, if for any adjacent vertex has a different sum of colors, then the coloring is a neighbor sum distinguishing [k]-edge coloring of G. For a proper [k]-total coloring of a graph G, if for any adjacent vertex has a different sum of colors, then the coloring is a neighbor sum distinguishing [k]-total coloring of G . In this paper, the coloring method and coloring index are determined by the process of induction and deduction and the construction of the dyeing method, and then the rationality of the method is verified by inverse proof and mathematical induction. If G is a simple graph with the order n ≥ 5 , and hn = (Hi ) i∈{1,2,…,n} is a sequence of disjoint simple graphs, where every Hi is a simple graph with the order m ≥ 7 . In this paper, we study the neighbor sum distinguishing edge(total) coloring of the generalized corona product G○hn of G and hn . The results are as follows: (1) If G is a path with order n , hn = (Hi ) i∈{1,2,…,n} is an alternating sequence of path and cycle with order m . If n is odd, we have χ Σ ′ ( G ∘ h n ) = m + 3 (2) If G is a path with order n , hn = (Hi ) i∈{1,2,…,n} is an alternating sequence of path and cycle with order m . If n is odd, we have χ Σ ′ ′ ( G ∘ h n ) = m + 4 Due to the late development of neighbor sum distinguishing edge (total) coloring of graphs, the related research results are relatively few. By studying the operation graph of a basic simple graph, we can provide the research basis and reference idea for the corresponding coloring of the general graph class. Therefore, it is of theoretical value to study the neighbor sum distinguishing edge (total) coloring problem of generalized corona products of graphs.

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

Calamoneri, Tiziana y Rossella Petreschi. "Edge-clique graphs and the lambda-coloring problem". Journal of the Brazilian Computer Society 7, n.º 3 (2001): 38–47. http://dx.doi.org/10.1590/s0104-65002001000200006.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

17

OSAWA, Hiroki, Akira SUZUKI, Takehiro ITO y Xiao ZHOU. "The Complexity of (List) Edge-Coloring Reconfiguration Problem". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E101.A, n.º 1 (2018): 232–38. http://dx.doi.org/10.1587/transfun.e101.a.232.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

18

CHEN, Qin. "Efficient algorithms for the edge-cover coloring problem". SCIENTIA SINICA Mathematica 46, n.º 3 (1 de marzo de 2016): 351–70. http://dx.doi.org/10.1360/012015-21.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

19

Lee, Sang-Un. "A Polynomial Time Algorithm for Edge Coloring Problem". Journal of the Korea Society of Computer and Information 18, n.º 11 (29 de noviembre de 2013): 159–65. http://dx.doi.org/10.9708/jksci.2013.18.11.159.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

20

Liu, Jia-Bao, Micheal Arockiaraj y Antony Nelson. "Tight Bounds on 1-Harmonious Coloring of Certain Graphs". Symmetry 11, n.º 7 (15 de julio de 2019): 917. http://dx.doi.org/10.3390/sym11070917.

Texto completo

Resumen

Graph coloring is one of the most studied problems in graph theory due to its important applications in task scheduling and pattern recognition. The main aim of the problem is to assign colors to the elements of a graph such as vertices and/or edges subject to certain constraints. The 1-harmonious coloring is a kind of vertex coloring such that the color pairs of end vertices of every edge are different only for adjacent edges and the optimal constraint that the least number of colors is to be used. In this paper, we investigate the graphs in which we attain the sharp bound on 1-harmonious coloring. Our investigation consists of a collection of basic graphs like a complete graph, wheel, star, tree, fan, and interconnection networks such as a mesh-derived network, generalized honeycomb network, complete multipartite graph, butterfly, and Benes networks. We also give a systematic and elegant way of coloring for these structures.

Los estilos APA, Harvard, Vancouver, ISO, etc.

21

Vikram, S. T. y S. Balaji. "An Analysis of the Factors Influencing the Strong Chromatic Index of Graphs Derived by Inflating a Few Common Classes of Graphs". Symmetry 15, n.º 7 (23 de junio de 2023): 1301. http://dx.doi.org/10.3390/sym15071301.

Texto completo

Resumen

The problem of strong edge coloring discusses assigning colors to the edges of a graph such that distinct colors are assigned to any two edges which are either adjacent to each other or are adjacent to a common edge. The least number of colors required to define a strong edge coloring of a graph is called its strong chromatic index. This problem is equivalent to the problem of assigning collision-free frequencies to the links between the elements of a wireless sensor network. In this article, we discuss a novel way of generating new graphs from existing graphs. This graph construction is known as inflating a graph. We discuss the strong chromatic index of graphs generated by inflating some common classes of graphs and graphs derived from them. In particular, we consider the cycle graph, which is symmetric in nature, and graphs such as the path graph and the star graph, which are not symmetric. Further, we analyze the factors which influence the strong chromatic index of these inflated graphs.

Los estilos APA, Harvard, Vancouver, ISO, etc.

22

Maus, Yannic. "The power of locality: Exploring the limits of randomness in distributed computing". it - Information Technology 62, n.º 5-6 (16 de diciembre de 2020): 271–78. http://dx.doi.org/10.1515/itit-2019-0051.

Texto completo

Resumen

AbstractMany modern systems are built on top of large-scale networks like the Internet. This article provides an overview of a dissertation [29] that addresses the complexity of classic graph problems like the vertex coloring problem in such networks. It has been known for a long time that randomization helps significantly in solving many of these problems, whereas the best known deterministic algorithms have been exponentially slower. In the first part of the dissertation we use a complexity theoretic approach to show that several problems are complete in the following sense: An efficient deterministic algorithm for any complete problem would imply an efficient algorithm for all problems that can be solved efficiently with a randomized algorithm. Among the complete problems is a rudimentary looking graph coloring problem that can be solved by a randomized algorithm without any communication. In further parts of the dissertation we develop efficient distributed algorithms for several problems where the most important problems are distributed versions of integer linear programs, the vertex coloring problem and the edge coloring problem. We also prove a lower bound on the runtime of any deterministic algorithm that solves the vertex coloring problem in a weak variant of the standard model of the area.

Los estilos APA, Harvard, Vancouver, ISO, etc.

23

Dey, Arindam, Le Son, P. Kumar, Ganeshsree Selvachandran y Shio Quek. "New Concepts on Vertex and Edge Coloring of Simple Vague Graphs". Symmetry 10, n.º 9 (1 de septiembre de 2018): 373. http://dx.doi.org/10.3390/sym10090373.

Texto completo

Resumen

The vague graph has found its importance as a closer approximation to real life situations. A review of the literature in this area reveals that the edge coloring problem for vague graphs has not been studied until now. Therefore, in this paper, we analyse the concept of vertex and edge coloring on simple vague graphs. Specifically, two new definitions for vague graphs related to the concept of the λ-strong-adjacent and ζ-strong-incident of vague graphs are introduced. We consider the color classes to analyze the coloring on the vertices in vague graphs. The proposed method illustrates the concept of coloring on vague graphs, using the definition of color class, which depends only on the truth membership function. Applications of the proposal in solving practical problems related to traffic flow management and the selection of advertisement spots are mainly discussed.

Los estilos APA, Harvard, Vancouver, ISO, etc.

24

Lestari, Dia y I. Ketut Budayasa. "BILANGAN KETERHUBUNGAN PELANGI PADA PEWARNAAN-SISI GRAF". MATHunesa: Jurnal Ilmiah Matematika 8, n.º 1 (23 de abril de 2020): 25–34. http://dx.doi.org/10.26740/mathunesa.v8n1.p25-34.

Texto completo

Resumen

Let be a graph. An edge-coloring of is a function , where is a set of colors. Respect to a subgraph of is called a rainbow subgraph if all edges of get different colors. Graph is called rainbow connected if for every two distinct vertices of is joined by a rainbow path. The rainbow connection number of , denoted by , is the minimum number of colors needed in coloring all edges of such that is a rainbow connected. The main problem considered in this thesis is determining the rainbow connection number of graph. In this thesis, we determine the exact value of the rainbow connection number of some classes of graphs such as Cycles, Complete graph, and Tree. We also determining the lower bound and upper bound for the rainbow connection number of graph. Keywords: Rainbow Connection Number, Graph, Edge-Coloring on Graph.

Los estilos APA, Harvard, Vancouver, ISO, etc.

25

Liang, Weifa. "Fast parallel algorithms for the approximate edge-coloring problem". Information Processing Letters 55, n.º 6 (septiembre de 1995): 333–38. http://dx.doi.org/10.1016/0020-0190(95)00122-s.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

26

Lucarelli, Giorgio y Ioannis Milis. "Improved approximation algorithms for the Max Edge-Coloring problem". Information Processing Letters 111, n.º 16 (agosto de 2011): 819–23. http://dx.doi.org/10.1016/j.ipl.2011.05.019.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

27

Cheng, Zhen, Zhihua Chen, Yufang Huang, Xuncai Zhang y Jin Xu. "Implementation of the Timetable Problem Using Self-assembly of DNA Tiles". International Journal of Computers Communications & Control 5, n.º 4 (1 de noviembre de 2010): 490. http://dx.doi.org/10.15837/ijccc.2010.4.2507.

Texto completo

Resumen

DNA self-assembly is a promising paradigm for nanotechnology. Recently, many researches demonstrate that computation by self-assembly of DNA tiles may be scalable. In this paper, we show how the tile self-assembly process can be used for implementing the timetable problem. First the timetable problem can be converted into the graph edge coloring problem with some constraints, then we give the tile self-assembly model by constructing three small systems including nondeterministic assigning system, copy system and detection system to perform the graph edge coloring problem, thus the algorithm is proposed which can be successfully solved the timetable problem with the computation time complexity ofΘ(mn), parallely and at very low cost.

Los estilos APA, Harvard, Vancouver, ISO, etc.

28

NAKANO, SHIN-ICHI y TAKAO NISHIZEKI. "SCHEDULING FILE TRANSFERS UNDER PORT AND CHANNEL CONSTRAINTS". International Journal of Foundations of Computer Science 04, n.º 02 (junio de 1993): 101–15. http://dx.doi.org/10.1142/s0129054193000079.

Texto completo

Resumen

The file transfer scheduling problem was introduced and studied by Coffman, Garey, Johnson and LaPaugh. The problem is to schedule transfers of a large collection of files between various nodes of a network under port constraint so as to minimize the overall finishing time. This paper extends their model to include communication channel constraint in addition to port constraint. We formulate the problem with both port and channel constraints as a new type of edge-coloring of multigraphs, called an fg-edge-coloring, and give an efficient approximation algorithm with absolute worst-case ratio 3/2.

Los estilos APA, Harvard, Vancouver, ISO, etc.

29

Malyshev, D. S. "Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem". Diskretnyi analiz i issledovanie operatsii 27, n.º 4 (30 de noviembre de 2020): 104–30. http://dx.doi.org/10.33048/daio.2020.27.682.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

30

Xie, Xuzhen, Mutsunori Yagiura, Takao Ono, Tomio Hirata y Uri Zwick. "An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem". Journal of Graph Algorithms and Applications 12, n.º 4 (2008): 383–99. http://dx.doi.org/10.7155/jgaa.00171.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

31

Ananda, Rizky, Zulfahmi Indra y Hamidah Nasution. "Application of Graph Coloring on Nurse Work Scheduling at H. Adam Malik Hospital Medan Using the Tabu Search Algorithm". ZERO: Jurnal Sains, Matematika dan Terapan 6, n.º 1 (23 de septiembre de 2022): 1. http://dx.doi.org/10.30829/zero.v6i1.12451.

Texto completo

Resumen

<p>Complex problems that usually occur in every hospital, one of which is scheduling with so many aspects, for example: the number of nurses, the distribution of nurse shifts, time off or leave and others. With the manual method that is still used in compiling the nurse's work schedule, it makes it difficult for an irregular and regular schedule. In solving the scheduling problem, the graph coloring method can be used. This scheduling problem can be solved by graph coloring. One solution to solve the problem of concluding graphs in scheduling is the Tabu Search Algorithm. A method that works as an effective problem solving method in finding the best solution to a problem. A method is used to solve the problem by making a representation in the form of a graph where the nurse is a node and grouping nurses as an edge by implementing the graph coloring into the Tabu Search Algorithm.</p>

Los estilos APA, Harvard, Vancouver, ISO, etc.

32

Malyshev, D. S. "Complete Complexity Dichotomy for $$\boldsymbol 7 $$-Edge Forbidden Subgraphs in the Edge Coloring Problem". Journal of Applied and Industrial Mathematics 14, n.º 4 (noviembre de 2020): 706–21. http://dx.doi.org/10.1134/s1990478920040092.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

33

Dobrinen, Natasha. "The Ramsey theory of the universal homogeneous triangle-free graph". Journal of Mathematical Logic 20, n.º 02 (28 de enero de 2020): 2050012. http://dx.doi.org/10.1142/s0219061320500129.

Texto completo

Resumen

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math. 38(1) (1971) 69–83] and denoted [Formula: see text], is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.[Formula: see text] , eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica 26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica 26(2) (2006) 183–205], the Ramsey theory of [Formula: see text] had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin. 2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph [Formula: see text], there is a finite number [Formula: see text] such that for any coloring of all copies of [Formula: see text] in [Formula: see text] into finitely many colors, there is a subgraph of [Formula: see text] which is again universal homogeneous triangle-free in which the coloring takes no more than [Formula: see text] colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code [Formula: see text] and the development of their Ramsey theory.

Los estilos APA, Harvard, Vancouver, ISO, etc.

34

Nagarathinam, R., N. Parvathi y . "Grundy Number of Some Chordal Graphs". International Journal of Engineering & Technology 7, n.º 4.10 (2 de octubre de 2018): 64. http://dx.doi.org/10.14419/ijet.v7i4.10.20708.

Texto completo

Resumen

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c : V → {1, 2, . . .} such that c(u) 12â‰ "> c(v) for every edge uv ∈ E. For proper coloring, colors assigned must be minimum, but for Grundy coloring which should be maximum. In this instance, Grundy numbers of chordal graphs like Cartesian product of two path graphs, join of the path and complete graphs and the line graph of tadpole have been executed

Los estilos APA, Harvard, Vancouver, ISO, etc.

35

Barenboim, Leonid, Michael Elkin y Uri Goldenberg. "Locally-iterative Distributed (Δ + 1)-coloring and Applications". Journal of the ACM 69, n.º 1 (28 de febrero de 2022): 1–26. http://dx.doi.org/10.1145/3486625.

Texto completo

Resumen

We consider graph coloring and related problems in the distributed message-passing model. Locally-iterative algorithms are especially important in this setting. These are algorithms in which each vertex decides about its next color only as a function of the current colors in its 1-hop-neighborhood . In STOC’93 Szegedy and Vishwanathan showed that any locally-iterative Δ + 1-coloring algorithm requires Ω (Δ log Δ + log * n ) rounds, unless there exists “a very special type of coloring that can be very efficiently reduced” [ 44 ]. No such special coloring has been found since then. This led researchers to believe that Szegedy-Vishwanathan barrier is an inherent limitation for locally-iterative algorithms and to explore other approaches to the coloring problem [ 2 , 3 , 19 , 32 ]. The latter gave rise to faster algorithms, but their heavy machinery that is of non-locally-iterative nature made them far less suitable to various settings. In this article, we obtain the aforementioned special type of coloring. Specifically, we devise a locally-iterative Δ + 1-coloring algorithm with running time O (Δ + log * n ), i.e., below Szegedy-Vishwanathan barrier. This demonstrates that this barrier is not an inherent limitation for locally-iterative algorithms. As a result, we also achieve significant improvements for dynamic, self-stabilizing, and bandwidth-restricted settings. This includes the following results: We obtain self-stabilizing distributed algorithms for Δ + 1-vertex-coloring, (2Δ - 1)-edge-coloring, maximal independent set, and maximal matching with O (Δ + log * n ) time. This significantly improves previously known results that have O(n) or larger running times [ 23 ]. We devise a (2Δ - 1)-edge-coloring algorithm in the CONGEST model with O (Δ + log * n ) time and O (Δ)-edge-coloring in the Bit-Round model with O (Δ + log n ) time. The factors of log * n and log n are unavoidable in the CONGEST and Bit-Round models, respectively. Previously known algorithms had superlinear dependency on Δ for (2Δ - 1)-edge-coloring in these models. We obtain an arbdefective coloring algorithm with running time O (√ Δ + log * n ). Such a coloring is not necessarily proper, but has certain helpful properties. We employ it to compute a proper (1 + ε)Δ-coloring within O (√ Δ + log * n ) time and Δ + 1-coloring within O (√ Δ log Δ log * Δ + log * n ) time. This improves the recent state-of-the-art bounds of Barenboim from PODC’15 [ 2 ] and Fraigniaud et al. from FOCS’16 [ 19 ] by polylogarithmic factors. Our algorithms are applicable to the SET-LOCAL model [ 25 ] (also known as the weak LOCAL model). In this model a relatively strong lower bound of Ω (Δ 1/3 ) is known for Δ + 1-coloring. However, most of the coloring algorithms do not work in this model. (In Reference [ 25 ] only Linial’s O (Δ 2 )-time algorithm and Kuhn-Wattenhofer O (Δ log Δ)-time algorithms are shown to work in it.) We obtain the first linear-in-Δ Δ + 1-coloring algorithms that work also in this model.

Los estilos APA, Harvard, Vancouver, ISO, etc.

36

Asratian, A. S. "Some results on an edge coloring problem of Folkman and Fulkerson". Discrete Mathematics 223, n.º 1-3 (agosto de 2000): 13–25. http://dx.doi.org/10.1016/s0012-365x(00)00061-3.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

37

Adamaszek, Anna y Alexandru Popa. "Approximation and hardness results for the maximum edge q-coloring problem". Journal of Discrete Algorithms 38-41 (mayo de 2016): 1–8. http://dx.doi.org/10.1016/j.jda.2016.09.003.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

38

de Oliveira Contiero, Lucas, Carlos Hoppen, Hanno Lefmann y Knut Odermann. "Stability of extremal hypergraphs with applications to an edge-coloring problem". Electronic Notes in Discrete Mathematics 61 (agosto de 2017): 263–69. http://dx.doi.org/10.1016/j.endm.2017.06.047.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

39

Borghini, Fabrizio, Isabel Méndez-Díaz y Paula Zabala. "An exact algorithm for the edge coloring by total labeling problem". Annals of Operations Research 286, n.º 1-2 (25 de julio de 2018): 11–31. http://dx.doi.org/10.1007/s10479-018-2977-x.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

40

Quaddoura, Ruzayn. "On 2-Colorability Problem for Hypergraphs with P_8-free Incidence Graphs". International Arab Journal of Information Technology 17, n.º 2 (28 de febrero de 2019): 257–63. http://dx.doi.org/10.34028/iajit/17/2/14.

Texto completo

Resumen

A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. The hypergraph 2- Coloring Problem is the question whether a given hypergraph is 2-colorable. It is known that deciding the 2-colorability of hypergraphs is NP-complete even for hypergraphs whose hyperedges have size at most 3. In this paper, we present a polynomial time algorithm for deciding if a hypergraph, whose incidence graph is P_8-free and has a dominating set isomorphic to C_8, is 2-colorable or not. This algorithm is semi generalization of the 2-colorability algorithm for hypergraph, whose incidence graph is P_7-free presented by Camby and Schaudt.

Los estilos APA, Harvard, Vancouver, ISO, etc.

41

Ardelean, Sebastian Mihai y Mihai Udrescu. "Graph coloring using the reduced quantum genetic algorithm". PeerJ Computer Science 7 (3 de enero de 2022): e836. http://dx.doi.org/10.7717/peerj-cs.836.

Texto completo

Resumen

Genetic algorithms (GA) are computational methods for solving optimization problems inspired by natural selection. Because we can simulate the quantum circuits that implement GA in different highly configurable noise models and even run GA on actual quantum computers, we can analyze this class of heuristic methods in the quantum context for NP-hard problems. This paper proposes an instantiation of the Reduced Quantum Genetic Algorithm (RQGA) that solves the NP-hard graph coloring problem in O(N1/2). The proposed implementation solves both vertex and edge coloring and can also determine the chromatic number (i.e., the minimum number of colors required to color the graph). We examine the results, analyze the algorithm convergence, and measure the algorithm's performance using the Qiskit simulation environment. Our Reduced Quantum Genetic Algorithm (RQGA) circuit implementation and the graph coloring results show that quantum heuristics can tackle complex computational problems more efficiently than their conventional counterparts.

Los estilos APA, Harvard, Vancouver, ISO, etc.

42

Yegnanarayanan, Venkataraman, Gayathri Yegnanarayanan y Marius Balas. "On Coloring Catalan Number Distance Graphs and Interference Graphs". Symmetry 10, n.º 10 (9 de octubre de 2018): 468. http://dx.doi.org/10.3390/sym10100468.

Texto completo

Resumen

A vertex coloring of a graph G is a mapping that allots colors to the vertices of G. Such a coloring is said to be a proper vertex coloring if two vertices joined by an edge receive different colors. The chromatic number χ ( G ) is the least number of colors used in a proper vertex coloring. In this paper, we compute the χ of certain distance graphs whose distance set elements are (a) a finite set of Catalan numbers, (b) a finite set of generalized Catalan numbers, (c) a finite set of Hankel transform of a transformed sequence of Catalan numbers. Then while discussing the importance of minimizing interference in wireless networks, we probe how a vertex coloring problem is related to minimizing vertex collisions and signal clashes of the associated interference graph. Then when investigating the χ of certain G ( V , D ) and graphs with interference, we also compute certain lower and upper bound for χ of any given simple graph in terms of the average degree and Laplacian operator. Besides obtaining some interesting results we also raised some open problems.

Los estilos APA, Harvard, Vancouver, ISO, etc.

43

Hebrard, Emmanuel y George Katsirelos. "Constraint and Satisfiability Reasoning for Graph Coloring". Journal of Artificial Intelligence Research 69 (4 de septiembre de 2020): 33–65. http://dx.doi.org/10.1613/jair.1.11313.

Texto completo

Resumen

Graph coloring is an important problem in combinatorial optimization and a major component of numerous allocation and scheduling problems. In this paper we introduce a hybrid CP/SAT approach to graph coloring based on the addition-contraction recurrence of Zykov. Decisions correspond to either adding an edge between two non-adjacent vertices or contracting these two vertices, hence enforcing inequality or equality, respectively. This scheme yields a symmetry-free tree and makes learnt clauses stronger by not committing to a particular color. 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; a branching heuristic emulating Br´elaz’ heuristic on the Zykov tree; and dedicated pruning techniques relying on marginal costs with respect to the bound and on reasoning about transitivity when unit propagating learnt clauses. The combination of these techniques in both a branch-and-bound and in a bottom-up search outperforms other SAT-based approaches and Dsatur on standard benchmarks both for finding upper bounds and for proving lower bounds.

Los estilos APA, Harvard, Vancouver, ISO, etc.

44

Wang, Zhaocai, Zuwen Ji, Ziyi Su, Xiaoming Wang y Kai Zhao. "Solving the maximal matching problem with DNA molecules in Adleman–Lipton model". International Journal of Biomathematics 09, n.º 02 (14 de enero de 2016): 1650019. http://dx.doi.org/10.1142/s1793524516500194.

Texto completo

Resumen

The maximal matching problem (MMP) is to find maximal edge subsets in a given undirected graph, that no pair of edges are adjacent in the subsets. It is a vitally important NP-complete problem in graph theory and applied mathematics, having numerous real life applications in optimal combination and linear programming fields. It can be difficultly solved by the electronic computer in exponential level time. Meanwhile in previous studies deoxyribonucleic acid (DNA) molecular operations usually were used to solve NP-complete continuous path search problems, e.g. HPP, traveling salesman problem, rarely for NP-hard problems with discrete vertices or edges solutions, such as the minimum vertex cover problem, graph coloring problem and so on. In this paper, we present a DNA algorithm for solving the MMP with DNA molecular operations. For an undirected graph with [Formula: see text] vertices and [Formula: see text] edges, we reasonably design fixed length DNA strands representing vertices and edges of the graph, take appropriate steps and get the solutions of the MMP in proper length range using [Formula: see text] time. We extend the application of DNA molecular operations and simultaneously simplify the complexity of the computation.

Los estilos APA, Harvard, Vancouver, ISO, etc.

45

Calamoneri, Tiziana. "Optimal L(j,k)-Edge-Labeling of Regular Grids". International Journal of Foundations of Computer Science 26, n.º 04 (junio de 2015): 523–35. http://dx.doi.org/10.1142/s012905411550029x.

Texto completo

Resumen

Given a graph [Formula: see text] and two positive integers j and k, an [Formula: see text]-edge-labeling is a function f assigning to edges of E colors from a set [Formula: see text] such that [Formula: see text] if e and e′ are adjacent, i.e. they share a common endpoint, [Formula: see text] if e and e′ are not adjacent and there exists an edge adjacent to both e and e′. The aim of the [Formula: see text]-edge-labeling problem consists of finding a coloring function f such that the value of [Formula: see text] is minimum. This minimum value is called [Formula: see text]. This problem has already been studied on hexagonal, squared and triangular grids, but mostly not coinciding upper and lower bounds on [Formula: see text] have been proposed. In this paper we close some of these gaps or find better bounds on [Formula: see text] in the special cases [Formula: see text] and [Formula: see text]. Moreover, we propose tight [Formula: see text]-edge-labelings for eight-regular grids.

Los estilos APA, Harvard, Vancouver, ISO, etc.

46

Janczewski, Robert y Michał Małafiejski. "On Efficient Coloring of Chordless Graphs". Decision Making in Manufacturing and Services 3, n.º 2 (21 de diciembre de 2009): 5–14. http://dx.doi.org/10.7494/dmms.2009.3.2.5.

Texto completo

Resumen

We are given a simple graph G = (V, E). Any edge e ∈ E is a chord in a path P ⊆ G (cycle C ⊆ G) iff a graph obtained by joining e to path P (cycle C) has exactly two vertices of degree 3. A class of graphs without any chord in paths (cycles) we call path-chordless (cycle-chordless). We will prove that recognizing and coloring of these graphs can be done in O(n2) and O(n) time, respectively. Our study was motivated by a wide range of applications of the graph coloring problem in coding theory, time tabling and scheduling, frequency assignment, register allocation and many other areas.

Los estilos APA, Harvard, Vancouver, ISO, etc.

47

PAUL, VIJI y K. A. GERMINA. "ON EDGE COLORING OF HYPERGRAPHS AND ERDÖS–FABER–LOVÁSZ CONJECTURE". Discrete Mathematics, Algorithms and Applications 04, n.º 01 (marzo de 2012): 1250003. http://dx.doi.org/10.1142/s1793830912500036.

Texto completo

Resumen

The celebrated Erdös–Faber–Lovász conjecture originated in the year 1972. It can be stated as follows: any linear hypergraph on n vertices has chromatic index at most n. Different formulations of the conjecture have been obtained and the conjecture is proved to be true in some particular cases. But the problem is still unsolved in general. In this paper, we prove that the conjecture is true for all linear hypergraphs on n vertices with [Formula: see text]. It generalizes an existing result regarding an equivalent formulation of the conjecture for dense hypergraphs [A. Sanchez-Arroyo, The Erdös–Faber–Lovász conjecture for dense hypergraphs, Discrete Math.308 (2008) 991–992].

Los estilos APA, Harvard, Vancouver, ISO, etc.

48

Ngo, Hung Q. y Van H. Vu. "Multirate Rearrangeable Clos Networks and a Generalized Edge-Coloring Problem on Bipartite Graphs". SIAM Journal on Computing 32, n.º 4 (enero de 2003): 1040–49. http://dx.doi.org/10.1137/s0097539702408235.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

49

Matsumoto, Yusuke, Naoyuki Kamiyama y Keiko Imai. "An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem". Information Processing Letters 111, n.º 10 (abril de 2011): 465–68. http://dx.doi.org/10.1016/j.ipl.2011.02.006.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

50

Sotskov, Yuri N. y Evangelina I. Mihova. "Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem". Algorithms 14, n.º 8 (19 de agosto de 2021): 246. http://dx.doi.org/10.3390/a14080246.

Texto completo

Resumen

This article extends the scheduling problem with dedicated processors, unit-time tasks, and minimizing maximal lateness Lmax for integer due dates to the scheduling problem, where along with precedence constraints given on the set V={v1,v2, …,vn} of the multiprocessor tasks, a subset of tasks must be processed simultaneously. Contrary to a classical shop-scheduling problem, several processors must fulfill a multiprocessor task. Furthermore, two types of the precedence constraints may be given on the task set V. We prove that the extended scheduling problem with integer release times ri≥0 of the jobs V to minimize schedule length Cmax may be solved as an optimal mixed graph coloring problem that consists of the assignment of a minimal number of colors (positive integers) {1,2, …,t} to the vertices {v1,v2, …,vn}=V of the mixed graph G=(V,A, E) such that, if two vertices vp and vq are joined by the edge [vp,vq]∈E, their colors have to be different. Further, if two vertices vi and vj are joined by the arc (vi,vj)∈A, the color of vertex vi has to be no greater than the color of vertex vj. We prove two theorems, which imply that most analytical results proved so far for optimal colorings of the mixed graphs G=(V,A, E), have analogous results, which are valid for the extended scheduling problems to minimize the schedule length or maximal lateness, and vice versa.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!