A 2nd-order conditional k-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least 2 in G will be adjacent to vertices with at least 2 different colors. The smallest ...
详细信息
A 2nd-order conditional k-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least 2 in G will be adjacent to vertices with at least 2 different colors. The smallest number k for which a graph G can have a 2nd-order conditional k-coloring is the 2nd-order conditional chromatic number, denoted by X-d (G). in this paper, we investigate the 2nd-order conditional 3-colorings of claw-free graphs. First, we prove that it is NP-complete to determine if a claw-free graph with maximum degree 3 is 2nd-order conditionally 3-colorable. Second, by forbidding a kind of subgraphs, we find a reasonable subclass of claw-free graphs with maximum degree 3, for which the 2nd-order conditionally 3-colorable problem can be solved in lineartime. Third, we give a linear time algorithm to recognize this subclass of graphs, and a linear time algorithm to determine whether it is 2nd-order conditionally 3-colorable. We also give a linear time algorithm to color the graphs in the subclass by 3 colors. (C) 2008 Elsevier B.V. All rights reserved.
Let C be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph G is an element of C with n vertices, finds a simple cycle of size k in G (if exists) in 2(O(k))n time. The algorit...
详细信息
Let C be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph G is an element of C with n vertices, finds a simple cycle of size k in G (if exists) in 2(O(k))n time. The algorithm applies to both directed and undirected graphs. In previous linear time algorithms for this problem, the runtime dependence on k is super-exponential. The algorithm can be derandomized yielding a 2(O(k))n log n timealgorithm. (C) 2020 Elsevier B.V. All rights reserved.
In this paper, we study the k-tuple domination in interval graphs from an algorithmic point of view. We present a linear time algorithm to solve the k-tuple domination problem in interval graphs for any positive integ...
详细信息
In this paper, we study the k-tuple domination in interval graphs from an algorithmic point of view. We present a linear time algorithm to solve the k-tuple domination problem in interval graphs for any positive integer k. Surprisingly, the time complexity of our algorithm is not related to k. This generalizes and extends the results of Pramanik et al. (Int J Comb 2011:14, 2011).
A clique of a graph G is a set of pairwise adjacent vertices of G. A clique-coloring of G is an assignment of colors to the vertices of G in such a way that no inclusion-wise maximal clique of size at least two of G i...
详细信息
A clique of a graph G is a set of pairwise adjacent vertices of G. A clique-coloring of G is an assignment of colors to the vertices of G in such a way that no inclusion-wise maximal clique of size at least two of G is monochromatic. An equitable clique-coloring of G is a clique-coloring such that any two color classes differ in size by at most one. Bacso and Tuza proved that connected claw-free graphs with maximum degree at most four, other than chordless odd cycles of order greater than three, are 2-clique-colorable and a 2-clique-coloring can be found in O(n(2)) Bacso and Tuza (Discrete Math Theor Comput Sci 11(2):15-24, 2009). In this paper we prove that every connected claw-free graph with maximum degree at most four, not a chordless odd cycle of order greater than three, has an equitable 2-clique-coloring. In addition we improve the algorithm described in the paper mentioned by giving an equitable 2-clique-coloring in lineartime for this class of graphs.
A double Roman dominating function on a graph G = (V (G), E(G)) is a function f : V (G) -> (0, 1, 2, 3) satisfying the property that every vertex assigned 0 has at least two neighbors assigned 2 or one neighbor ass...
详细信息
A double Roman dominating function on a graph G = (V (G), E(G)) is a function f : V (G) -> (0, 1, 2, 3) satisfying the property that every vertex assigned 0 has at least two neighbors assigned 2 or one neighbor assigned 3, and every vertex assigned 1 has at least one neighbor assigned 2 or 3. A double Roman dominating function f is called a restrained double Roman dominating function (RDRD-function) if the induced subgraph of G by the vertices assigned 0 under f has no isolated vertex. The weight of an RDRD-function f is the value omega(f) = Sigma(v is an element of V(G)) f (v), and the minimum weight over all RDRD-functions on G is the restrained double Roman domination number (RDRD-number) gamma(rdR)(G) of G. In this paper, we first characterize the graphs with small RDRD-numbers and then show the sharp bounds of gamma(rdR)(G)+ gamma(rdR)((G) over bar) for any connected graph G with order at least 3. Finally, a linear time algorithm for computing the RDRD-number of any cograph is presented. These results partially answer two open problems posed by Mojdeh et al.
Given an undirected graph G and two vertex subsets H-1 and H-2, the bi-level augmentation problem is that of adding to G the smallest number of edges such that the resulting graph contains two internally vertex-disjoi...
详细信息
Given an undirected graph G and two vertex subsets H-1 and H-2, the bi-level augmentation problem is that of adding to G the smallest number of edges such that the resulting graph contains two internally vertex-disjoint paths between every pair of vertices in H-1 and two edge-disjoint paths between every pair of vertices in H-2. We present an algorithm to solve this problem in lineartime. By properly setting H-1 and H-2, this augmentation algorithm subsumes existing optimal algorithms for several graph augmentation problems.
A set of vertices D is a dominating set for a graph G = ( V , E ) if every vertex in V − D is adjacent to a vertex in D . A set of vertices D is a total dominating set if every vertex in V is adjacent to a vertex in D...
详细信息
A set of vertices D is a dominating set for a graph G = ( V , E ) if every vertex in V − D is adjacent to a vertex in D . A set of vertices D is a total dominating set if every vertex in V is adjacent to a vertex in D . Chang and Nemhauser gave a linear time algorithm to find a minimum cardinality dominating set for the κ-th power of a block graph. This paper presents a linear time algorithm for finding a minimum cardinality total dominating set of a block graph.
A path pi = (v(1), v(2), ... , v(k+1)) in a graph G = (V, E) is a downhill path if for every i, 1 = deg(v(i+1)), where deg(v(i)) denotes the degree of vertex v(i) is an element of V. A downhill dominating set DDS is a...
详细信息
A path pi = (v(1), v(2), ... , v(k+1)) in a graph G = (V, E) is a downhill path if for every i, 1 <= i <= k, deg(v(i)) >= deg(v(i+1)), where deg(v(i)) denotes the degree of vertex v(i) is an element of V. A downhill dominating set DDS is a set S subset of V having the property that every vertex v is an element of V lies on a downhill path originating from some vertex in S. The downhill domination number gamma(dn)(G) equals the minimum cardinality of a DDS of G. A DDS having minimum cardinality is called a gamma(dn)-set of G. In this note, we give an enumeration of all the distinct gamma(dn)-sets of G, and we show that there is a linear time algorithm to determine the downhill domination number of a graph. (c) 2015 Elsevier B.V. All rights reserved.
Let v be a vertex of a graph G;a transition graph T(v) of v is a graph whose vertices are the edges incident with v. We consider graphs G with prescribed transition systems T = {T(v) \ v is an element of V(G)}. A path...
详细信息
Let v be a vertex of a graph G;a transition graph T(v) of v is a graph whose vertices are the edges incident with v. We consider graphs G with prescribed transition systems T = {T(v) \ v is an element of V(G)}. A path P in G is called T-compatible, if each pair uv, vw of consecutive edges of P form an edge in T(v). Let A be a given class of graphs (closed under isomorphism). We study the computational complexity of finding T-compatible paths between two given vertices of a graph for a specified transition system T subset of or equal to A. Our main result is that a dichotomy holds (subject to the assumption P not equal NP). That is, for a considered class A, the problem is either (1) NP-complete, or (2) it can be solved in lineartime. We give a criterion-based on vertex induced subgraphs-which decides whether (1) or (2) holds for any given class A. (C) 2002 Elsevier Science B.V. All rights reserved.
Given two permutations of n elements, a pair of intervals of these permutations consisting of the same set of elements is called a common interval. Some genetic algorithms based on such common intervals have been prop...
详细信息
Given two permutations of n elements, a pair of intervals of these permutations consisting of the same set of elements is called a common interval. Some genetic algorithms based on such common intervals have been proposed for sequencing problems and have exhibited good prospects. In this paper we propose three types of fast algorithms to enumerate all common intervals: (i) a simple O (n(2)) timealgorithm (LHP), whose expected running time becomes O(n) for two randomly generated permutations, (ii) a practically fast O (n(2)) time alogrithm (MNG) using the reverse Monge property, and (iii) an O(n + K) timealgorithm (RC), where K (less than or equal to (n/2)) is the number of common intervals. It will also be shown that the expected number of common intervals for two random permutations is O(1). This result gives a reason for the phenomenon that the expected time complexity O(n) of the algorithm LHP is independent of K. Among the proposed algorithms, RC is most desirable from the theoretical point of view;however, it is quite complicated compared with LHP and MNG. Therefore, it is possible that RC is slower than the other two algorithms in some cases. For this reason, computational experiments for various types of problems with up to n = 10(6) are conducted. The results indicate that (i) LKP and MNG are much faster than RC for two randomly generated permutations, and (ii) MNG is rather slower than LHP for random inputs;however, there are cases in which LHP requires Omega(n(2)) time, but MNG runs in o(n(2)) time and is faster than both LHP and RC.
暂无评论