In this paper we study a generalization of the path cover problem, namely, the 2-terminal-set path cover problem, or 2TPC for short. Given a graph G and two disjoint subsets T-1 and T-2 of V(G), a 2-terminal-set path ...
详细信息
ISBN:
(纸本)9783540693109
In this paper we study a generalization of the path cover problem, namely, the 2-terminal-set path cover problem, or 2TPC for short. Given a graph G and two disjoint subsets T-1 and T-2 of V(G), a 2-terminal-set path cover of G with respect to T-1 and T-2 is a set of vertex-disjoint paths P that covers the vertices of G such that the vertices of T-1 and T-2 are all endpoints of the paths in P and all the paths with 2 both endpoints in T-1 boolean OR T-2 have one endpoint in T-1 and the other in T-2. The 2TPC problem is to find a 2-terminal-set path cover of G of minimum cardinality;note that, if T-1 boolean OR T-2 is empty, the stated problem coincides with the classical path cover problem. The 2TPC problem generalizes some path cover related problems, such as the 1HP and 2HP problems, which have been proved to be NP-complete even for small classes of graphs. We show that the 2TPC problem can be solved in lineartime on the class of cographs. The proposed linear-time algorithm is simple, requires linear space, and also enables us to solve the 1HP and 2HP problems on cographs within the same time and space complexity.
Suppose that we are given a positive integer k, and a k-(vertex-)colouring f 0 of a given graph G. Then we are asked to find a colouring of G using the minimum number of colours among colourings that are reachable fro...
详细信息
Suppose that we are given a positive integer k, and a k-(vertex-)colouring f 0 of a given graph G. Then we are asked to find a colouring of G using the minimum number of colours among colourings that are reachable from f 0 by iteratively changing a colour assignment of exactly one vertex while maintaining the property of k-colourings. In this paper, we give linear-time algorithms to solve the problem for graphs of degeneracy at most two and for the case where k = 3 . These results imply linear-time algorithms for series-parallel graphs and grid graphs. In addition, we give linear-time algorithms for chordal graphs and cographs. On the other hand, we show that, for any k = 4 , this problem remains NP-hard for planar graphs with degeneracy three and maximum degree four. Thus, we obtain a complexity dichotomy for this problem with respect to the degeneracy of a graph and the number k of colours.
A partition;= {V1, V2, ..., Vk} of the vertex set V of a graph G into k color classes Vi, with 1 < i < k is called a quorum coloring if for every vertex v is an element of V, at least half of the vertices in the...
详细信息
A partition;= {V1, V2, ..., Vk} of the vertex set V of a graph G into k color classes Vi, with 1 < i < k is called a quorum coloring if for every vertex v is an element of V, at least half of the vertices in the closed neighborhood N[v] of v have the same color as v. The maximum cardinality of a quorum coloring of G is called the quorum coloring number of G and is denoted by *q(G). A quorum coloring of order *q(G) is a *q-coloring. In this paper, we partially answer an open problem concerning quorum colorings of graphs. Namely, we improve a sharp lower bound given in 2012 by Eroh and Gera on the quorum coloring number of a nontrivial tree, and show that our new lower bound can be computed in lineartime. Moreover, we show that this bound is attained by all non trivial binary trees. (c) 2022 Elsevier B.V. All rights reserved.
Implementing graph algorithms efficiently in a rule-based language is challenging because graph pattern matching is expensive. In this paper, we present a number of linear-time implementations of graph algorithms in G...
详细信息
Implementing graph algorithms efficiently in a rule-based language is challenging because graph pattern matching is expensive. In this paper, we present a number of linear-time implementations of graph algorithms in GP 2, an experimental programming language based on graph transformation rules which aims to facilitate program analysis and verification. We focus on two classes of rule-based graph programs: graph reduction programs which check some graph property, and programs using a depth-first search to test some property or perform an operation such as producing a 2-colouring or a topological sorting. Programs of the first type run in lineartime without any constraints on input graphs while programs of the second type require input graphs of bounded degree to run in lineartime. Essential for achieving the lineartime complexity are so-called rooted rules in GP 2, which, in many situations, can be matched in constant time. For each of our programs, we prove both correctness and complexity, and also give empirical evidence for their runtime. (C) 2021 The Author(s). Published by Elsevier B.V.
The mpirical testing of a program often calls for generating a set of random numbers and then nnmedmtely sorting them. In this paper we consider the problem of accomplishing that process in a single step. generating a...
详细信息
We consider a problem in computational origami. Given a piece of paper as a convex polygon P and a point f located within, we fold every point on a boundary of P to f and compute a region that is safe from folding, i....
详细信息
We consider a problem in computational origami. Given a piece of paper as a convex polygon P and a point f located within, we fold every point on a boundary of P to f and compute a region that is safe from folding, i.e., the region with no creases. This problem is an extended version of a problem by Akitaya, Ballinger, Demaine, Hull, and Schmidt that only folds corners of the polygon. To find the region, we prove structural properties of intersections of parabola-bounded regions and use them to devise a linear-time algorithm. We also prove a structural result regarding the complexity of the safe region as a variable of the location of point f, i.e., the number of arcs of the safe region can be determined using the straight skeleton of the polygon P.
暂无评论