Log in

Relevant bibliographies by topics / Edge coloring problem / Journal articles

Journal articles on the topic 'Edge coloring problem'

To see the other types of publications on this topic, follow the link: 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:

Consult the top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

11

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

12

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

13

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

14

Zhou, Yangyang, Dongyang Zhao, Mingyuan Ma, and Jin Xu. "Domination Coloring of Graphs." Mathematics 10, no. 6 (March 21, 2022): 998. http://dx.doi.org/10.3390/math10060998.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

15

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

16

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

21

Vikram, S. T., and 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, no. 7 (June 23, 2023): 1301. http://dx.doi.org/10.3390/sym15071301.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

22

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

23

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

24

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

25

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

28

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

29

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Ananda, Rizky, Zulfahmi Indra, and 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, no. 1 (September 23, 2022): 1. http://dx.doi.org/10.30829/zero.v6i1.12451.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

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, no. 4 (November 2020): 706–21. http://dx.doi.org/10.1134/s1990478920040092.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

34

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

35

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

36

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

41

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

42

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

43

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

44

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

45

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

46

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

47

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

48

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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!