共查询到20条相似文献,搜索用时 46 毫秒
1.
Sourav Chakraborty Eldar Fischer Arie Matsliah Raphael Yuster 《Journal of Combinatorial Optimization》2011,21(3):330-347
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In the first result of this paper we prove that computing rc(G) is NP-Hard solving an open problem from Caro et al. (Electron. J. Comb. 15, 2008, Paper R57). In fact, we prove that it is already NP-Complete to decide if rc(G)=2, and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is
rainbow connected. On the positive side, we prove that for every ε>0, a connected graph with minimum degree at least ε
n has bounded rainbow connection, where the bound depends only on ε, and a corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open
problems and conjectures are also presented. 相似文献
2.
Given a graph G=(V,E) with node weight w:V→R
+ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard
and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n
O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a
polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs.
As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial
time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs. 相似文献
3.
An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for
an adjacent vertex distinguishing total coloring of G is denoted by χ″
a
(G). In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of outerplanar graphs. 相似文献
4.
Let G=(V,E) be a graph without isolated vertices. A set S⊆V is a paired-dominating set if every vertex in V−S is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum
cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng (Discrete Appl. Math.
155:2077–2086, 2007), we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs.
In addition, we prove that paired-domination problem is NP-complete for bipartite graphs, chordal graphs, even for split graphs. 相似文献
5.
Understanding recombination is a central problem in population genetics. In this paper, we address an established computational
problem in this area: compute lower bounds on the minimum number of historical recombinations for generating a set of sequences
(Hudson and Kaplan in Genetics 111, 147–164, 1985; Myers and Griffiths in Genetics 163, 375–394, 2003; Gusfield et al. in Discrete Appl. Math. 155, 806–830, 2007; Bafna and Bansal in IEEE/ACM Trans. Comput. Biol. Bioinf. 1, 78–90, 2004 and in J. Comput. Biol. 13, 501–521, 2006; Song et al. in Bioinformatics 421, i413–i244, 2005). In particular, we propose a new recombination lower bound: the forest bound. We show that the forest bound can be formulated
as the minimum perfect phylogenetic forest problem, a natural extension to the classic binary perfect phylogeny problem, which
may be of interests on its own. We then show that the forest bound is provably higher than the optimal haplotype bound (Myers
and Griffiths in Genetics 163, 375–394, 2003), a very good lower bound in practice (Song et al. in Bioinformatics 421, i413–i422, 2005). We prove that, like several other lower bounds (Bafna and Bansal in J. Comput. Biol. 13, 501–521, 2006), computing the forest bound is NP-hard. Finally, we describe an integer linear programming (ILP) formulation that computes
the forest bound precisely for certain range of data. Simulation results show that the forest bound may be useful in computing
lower bounds for low quality data.
A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 16–26.
The work was performed while Y. Wu was with UC Davis and supported by grants CCF-0515278 and IIS-0513910 from National Science
Foundation.
D. Gusfield supported by grants CCF-0515278 and IIS-0513910 from National Science Foundation. 相似文献
6.
Mathieu Bouchard Alain Hertz Guy Desaulniers 《Journal of Combinatorial Optimization》2009,17(2):168-191
An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S
v
(G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D
v
(G,c) the minimum number of integers which must be added to S
v
(G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑
v∈V
D
v
(G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds
on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a
tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them
having a known optimal deficiency. 相似文献
7.
Domingos M. Cardoso Marcin Kamiński Vadim Lozin 《Journal of Combinatorial Optimization》2007,14(4):455-463
Independent sets, induced matchings and cliques are examples of regular induced subgraphs in a graph. In this paper, we prove
that finding a maximum cardinality k-regular induced subgraph is an NP-hard problem for any fixed value of k. We propose a convex quadratic upper bound on the size of a k-regular induced subgraph and characterize those graphs for which this bound is attained. Finally, we extend the Hoffman bound
on the size of a maximum 0-regular subgraph (the independence number) from k=0 to larger values of k. 相似文献
8.
The problem of optimal surface flattening in 3-D finds many applications in engineering and manufacturing. However, previous
algorithms for this problem are all heuristics without any quality guarantee and the computational complexity of the problem
was not well understood. In this paper, we prove that the optimal surface flattening problem is NP-hard. Further, we show
that the problem of flattening a topologically spherical surface admits a PTAS and can be solved by a (1+ε)-approximation algorithm in O(nlog n) time for any constant ε>0, where n is the input size of the problem. 相似文献
9.
On backbone coloring of graphs 总被引:1,自引:0,他引:1
Weifan Wang Yuehua Bu Micka?l Montassier André Raspaud 《Journal of Combinatorial Optimization》2012,23(1):79-93
Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum
average degree, graphs with maximum degree 3, etc. 相似文献
10.
We study a new coloring concept which generalizes the classical vertex coloring problem in a graph by extending the notion
of stable sets to split graphs. First of all, we propose the packing problem of finding the split graph of maximum size where
a split graph is a graph G = (V,E) in which the vertex set V can be partitioned into a clique K and a stable set S. No condition is imposed on the edges linking vertices in S to the vertices in K. This maximum split graph problem gives rise to an associated partitioning problem that we call the split-coloring problem.
Given a graph, the objective is to cover all his vertices by a least number of split graphs. Definitions related to this new
problem are introduced. We mention some polynomially solvable cases and describe open questions on this area.
An erratum to this article is available at . 相似文献
11.
An adjacent vertex-distinguishing edge coloring of a graph is a proper edge coloring such that no pair of adjacent vertices meets the same set of colors. The adjacent vertex-distinguishing edge chromatic number is the minimum number of colors required for an adjacent vertex-distinguishing edge coloring, denoted as \(\chi '_{as}(G)\). In this paper, we prove that for a connected graph G with maximum degree \(\Delta \ge 3\), \(\chi '_{as}(G)\le 3\Delta -1\), which proves the previous upper bound. We also prove that for a graph G with maximum degree \(\Delta \ge 458\) and minimum degree \(\delta \ge 8\sqrt{\Delta ln \Delta }\), \(\chi '_{as}(G)\le \Delta +1+5\sqrt{\Delta ln \Delta }\). 相似文献
12.
In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n
o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal
and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of
\fracc3lnn\frac{c}{3}\ln{n} in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results
suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar
results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs. 相似文献
13.
Inapproximability results for the lateral gene transfer problem 总被引:1,自引:0,他引:1
Bhaskar Dasgupta Sergio Ferrarini Uthra Gopalakrishnan Nisha Raj Paryani 《Journal of Combinatorial Optimization》2006,11(4):387-405
This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallett and Lagergren (2001), is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. Our main results are the following:
This research was supported by NSF grants CCR-0296041, CCR-0206795, CCR-0208749 and IIS-0346973. 相似文献
(a) | We show that it is not possible to approximate the problem in polynomial time within an approximation ratio of 1 + ε, for some constant ε > 0 unless P = NP. We also provide explicit values of ε for the above claim. |
(b) | We provide an upper bound on the cost of any 1-active scenario and prove the tightness of this bound. |
14.
In this paper, we consider a new visual cryptography scheme that allows for sharing of multiple secret images on graphs: we
are given an arbitrary graph (V,E) where every node and every edge are assigned an arbitrary image. Images on the vertices are “public” and images on the edges
are “secret”. The problem that we are considering is how to make a construction such that when the encoded images of two adjacent
vertices are printed on transparencies and overlapped, the secret image corresponding to the edge is revealed. We define the
most stringent security guarantees for this problem (perfect secrecy) and show a general construction for all graphs where
the cost (in terms of pixel expansion and contrast of the images) is proportional to the chromatic number of the cube of the
underlying graph. For the case of bounded degree graphs, this gives us constant-factor pixel expansion and contrast. This
compares favorably to previous works, where pixel expansion and contrast are proportional to the number of images. 相似文献
15.
Carlos J. Luz 《Journal of Combinatorial Optimization》2011,22(4):882-894
This paper considers the NP-hard graph problem of determining a maximum cardinality subset of vertices inducing a k-regular subgraph. For any graph G, this maximum will be denoted by α
k
(G). From a well known Motzkin-Straus result, a relationship is deduced between α
k
(G) and the independence number α(G). Next, it is proved that the upper bounds υ
k
(G) introduced in Cardoso et al. (J. Comb. Optim., 14, 455–463, 2007) can easily be computed from υ
0(G), for any positive integer k. This relationship also allows one to present an alternative proof of the Hoffman bound extension introduced in the above
paper. The paper continues with the introduction of a new upper bound on α
k
(G) improving υ
k
(G). Due to the difficulty of computing this improved bound, two methods are provided for approximating it. Finally, some computational
experiments which were performed to compare all bounds studied are reported. 相似文献
16.
Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all
vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive
the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application
of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability
of this problem and prove Ω(g1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds.
Supported in part by the NSF of China under Grant No. 70221001 and 60373012. 相似文献
17.
Tao Wang 《Journal of Combinatorial Optimization》2017,33(3):1090-1105
A total coloring of a graph G is an assignment of colors to the vertices and the edges of G such that every pair of adjacent/incident elements receive distinct colors. The total chromatic number of a graph G, denoted by \(\chi ''(G)\), is the minimum number of colors in a total coloring of G. The well-known total coloring conjecture (TCC) says that every graph with maximum degree \(\Delta \) admits a total coloring with at most \(\Delta + 2\) colors. A graph is 1-toroidal if it can be drawn in torus such that every edge crosses at most one other edge. In this paper, we investigate the total coloring of 1-toroidal graphs, and prove that the TCC holds for the 1-toroidal graphs with maximum degree at least 11 and some restrictions on the triangles. Consequently, if G is a 1-toroidal graph with maximum degree \(\Delta \) at least 11 and without adjacent triangles, then G admits a total coloring with at most \(\Delta + 2\) colors. 相似文献
18.
Paul Dorbec Michael A. Henning Douglas F. Rall 《Journal of Combinatorial Optimization》2008,16(1):68-80
In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning,
M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ
t
(G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ
t
(G)Γ
t
(H)≤2Γ
t
(G □ H).
Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
19.
William S. Kennedy Hui Kong Guohui Lin Guiying Yan 《Journal of Combinatorial Optimization》2010,19(1):94-106
Inspired by phylogenetic tree construction in computational biology, Lin et al. (The 11th Annual International Symposium on
Algorithms and Computation (ISAAC 2000), pp. 539–551, 2000) introduced the notion of a k
-phylogenetic root. A k-phylogenetic root of a graph G is a tree T such that the leaves of T are the vertices of G, two vertices are adjacent in G precisely if they are within distance k in T, and all non-leaf vertices of T have degree at least three. The k-phylogenetic root problem is to decide whether such a tree T exists for a given graph G. In addition to introducing this problem, Lin et al. designed linear time constructive algorithms for k≤4, while left the problem open for k≥5. In this paper, we partially fill this hole by giving a linear time constructive algorithm to decide whether a given tree
chordal graph has a 5-phylogenetic root; this is the largest class of graphs known to have such a construction. 相似文献
20.
On lazy bureaucrat scheduling with common deadlines 总被引:1,自引:1,他引:0
Lazy bureaucrat scheduling is a new class of scheduling problems introduced by Arkin et al. (Inf. Comput. 184:129–146, 2003). In this paper we focus on the case where all the jobs share a common deadline. Such a problem is denoted as CD-LBSP, which
has been considered by Esfahbod et al. (Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66,
2003). We first show that the worst-case ratio of the algorithm SJF (Shortest Job First) is two under the objective function [min-time-spent], and thus answer an open question posed in (Esfahbod, et al. in Algorithms and data structures. Lecture notes in computer
science, vol. 2748, pp. 59–66, 2003). We further present two approximation schemes A
k
and B
k
both having worst-case ratio of
, for any given integer k>0, under the objective functions [min-makespan] and [min-time-spent], respectively. Finally, we prove that the problem CD-LBSP remains NP-hard under several objective functions, even if all
jobs share the same release time.
A preliminary version of the paper appeared in Proceedings of the 7th Latin American Symposium on Theoretical Informatics,
pp 515–523, 2006.
Research of G. Zhang supported in part by NSFC (60573020). 相似文献