共查询到20条相似文献,搜索用时 334 毫秒
1.
Let γ
t
{k}(G) denote the total {k}-domination number of graph G, and let
denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices,
. As a corollary of this result, we have
for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005).
The work was supported by NNSF of China (No. 10701068 and No. 10671191). 相似文献
2.
In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine
whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time
unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved
to
when the underlying graph G is an interval graph. 相似文献
3.
For plane triangulations, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G in the st-orientation is
(Zhang and He in Lecture Notes in Computer Science, vol. 3383, pp. 425–430, 2005). In this paper, we prove the bound
is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by
. In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height
, constructible in linear time, which is also optimal.
A preliminary version of this paper was presented at AAIM 2007. 相似文献
4.
Haiying Wang 《Journal of Combinatorial Optimization》2007,14(1):87-109
Let be a simple graph and T(G) be the set of vertices and edges of G. Let C be a k-color set. A (proper) total k-coloring f of G is a function such that no adjacent or incident elements of T(G) receive the same color. For any , denote . The total k-coloring f of G is called the adjacent vertex-distinguishing if for any edge . And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number of G. In this paper, we prove that for all connected graphs with maximum degree three. This is a step towards a conjecture on the adjacent vertex-distinguishing
total coloring.
MSC: 05C15 相似文献
5.
Paul Dorbec Sylvain Gravier Michael A. Henning 《Journal of Combinatorial Optimization》2007,14(1):1-7
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206).
A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs. 相似文献
6.
Hung Q. Ngo 《Journal of Combinatorial Optimization》2008,15(1):61-76
In this paper, we formulate and investigate the following problem: given integers d,k and r where k>r≥1,d≥2, and a prime power q, arrange d hyperplanes on
to maximize the number of r-dimensional subspaces of
each of which belongs to at least one of the hyperplanes. The problem is motivated by the need to give tighter bounds for
an error-tolerant pooling design based on finite vector spaces.
This work is partially supported by NSF CAREER Award CCF-0347565. 相似文献
7.
Hiroshi Nagamochi Takashi Shiraki Toshihide Ibaraki 《Journal of Combinatorial Optimization》2001,5(2):175-212
Given a finite set V and a set function
, we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function
together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in
time, where
is the time to compute the value of f(X) for a subset
. 相似文献
8.
The inverse 1-maxian problem with edge length modification 总被引:2,自引:1,他引:1
Elisabeth Gassner 《Journal of Combinatorial Optimization》2008,16(1):50-67
We consider the problem of modifying the lengths of the edges of a graph at minimum cost such that a prespecified vertex becomes
a 1-maxian with respect to the new edge lengths. The inverse 1-maxian problem with edge length modification is shown to be
strongly
-hard and remains weakly
-hard even on series-parallel graphs. Moreover, a transformation of the inverse 1-maxian problem with edge length modification
on a tree to a minimum cost circulation problem is given which solves the original problem in
.
This research has been supported by the Austrian Science Fund (FWF) Project P18918-N18. 相似文献
9.
Nguyen Bao Nguyen C. Thach Nguyen Wing-Kin Sung 《Journal of Combinatorial Optimization》2007,13(3):223-242
Consider two phylogenetic networks and ’ of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by and ’. This distance is proposed by Moret et al. (2004) and is a generalization of Robinson-Foulds distance, which is orginally
used to compare two phylogenetic trees. This paper gives an -time algorithm to compute this distance, where h is the number of hybrid nodes in and ’ while k is the maximum number of hybrid nodes among all biconnected components in and ’. Note that $k \ll h \ll n$ in a phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which
are an important, biological meaningful special case of phylogenetic network. We give an $O(n)$-time algorithm for comparing
two galled-trees. We also give an -time algorithm for comparing a galled-tree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively. 相似文献
10.
This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log 2
e(G)⌉≤t(G)≤⌈log 2
e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that
the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite
graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤24 or
for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤25 or
for k≥6.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013.
G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical
Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office. 相似文献
11.
Michael A. Henning 《Journal of Combinatorial Optimization》2007,13(1):61-78
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199–206. A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that if n ≥ 6, then . In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that and we characterize the (infinite family of) graphs that achieve equality in this bound.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
12.
It is known that
(Cai, 2001). The reverse direction of whether ZPPNP is contained in
remains open. We show that if the zero-error algorithm is allowed to ask only one query to the NP oracle (for any input and
random string), then it can be simulated in
. That is, we prove that
. Next we consider whether the above result can be improved as
and point out a difficulty in doing so. Via a simple proof, we observe that BPP ⊆ ZPPNP[1] (a result implicitly proven in some prior work). Thus, achieving the above improvement would imply BPP ⊆ PNP, settling a long standing open problem.
We then argue that the above mentioned improvement can be obtained for the next level of the polynomial time hierarchy. Namely,
we prove that
. On the other hand, by adapting our proof of our main result it can be shown that
. For the purpose of comparing these two results, we prove that
. We conclude by observing that the above claims extend to the higher levels of the hierarchy: for k ≥ 2,
and
.
Research supported in part by NSF grant CCR-0208013. A preliminary version of the paper was presented at COCOON′05 Cai and
Chakaravarthy (2005).
Part of the research was conducted while the author was at the University of Wisconsin, Madison. 相似文献
13.
In this paper, we construct a d
z
-disjunct matrix with subspaces in a dual space of Unitary space
, then give its several properties. As the smaller the ratio efficiency is, the better the pooling design is. We compare the
ratio efficiency of this construction with others, such as the ratio efficiency of the construction of set, the general space
and the dual space of symplectic space. In addition, we find it smaller under some conditions.
Supported by NSF of the Education Department of Hebei Province (2007127) and NSF of Hebei Normal University (L2004B04). 相似文献
14.
Given d>2 and a set of n grid points Q in ℜ
d
, we design a randomized algorithm that finds a w-wide separator, which is determined by a hyper-plane, in
sublinear time such that Q has at most
points on either side of the hyper-plane, and at most
points within
distance to the hyper-plane, where c
d
is a constant for fixed d. In particular, c
3=1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator
is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm
of Xu (Research in computational molecular biology, 9th annual international conference, pp. 408–422, 2005).
This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35.
The part of this research was done while Bin Fu was associated with the Department of Computer Science, University of New
Orleans, LA 70148, USA and the Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, USA. 相似文献
15.
Mohammad Khairul Hasan Hyunwoo Jung Kyung-Yong Chwa 《Journal of Combinatorial Optimization》2008,16(2):155-172
We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c
e
for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d
j
and a set of facilities F⊆V each has nonnegative opening cost f
i
and capacity to serve all client demands. The objective is to open a subset of facilities, say
, to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost
is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in
Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm. 相似文献
16.
Cai Mao-Cheng 《Journal of Combinatorial Optimization》1999,3(4):465-474
In this paper we study the inverse problem of matroid intersection: Two matroids M
1 = (E,
1) and M
2 = (E,
2), their intersection B, and a weight function w on E are given. We try to modify weight w, optimally and with bounds, such that B becomes a maximum weight intersection under the modified weight. It is shown in this paper that the problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved by strongly polynomial time algorithms. We also give a necessary and sufficient condition for the feasibility of the problem. Finally we extend the discussion to the version of the problem with Multiple Intersections. 相似文献
17.
An instance I of Ring Grooming consists of m sets A
1,A
2,…, A
m
from the universe {0, 1,…, n − 1} and an integer g ≥ 2. The unrestricted variant of Ring Grooming, referred to as Unrestricted Ring Grooming, seeks a partition {P
1 , P
2, …,P
k
} of {1, 2, …, m} such that for each 1 ≤ i ≤ k and is minimized. The restricted variant of Ring Grooming, referred to as Restricted Ring Grooming, seeks a partition of {1,2,…,m} such that | P
i
| ≤ g for each and is minimized. If g = 2, we provide an optimal polynomial-time algorithm for both variants. If g > 2, we prove that both both variants are NP-hard even with fixed g. When g is a power of two, we propose an approximation algorithm called iterative matching. Its approximation ratio is exactly 1.5
when g = 4, at most 2.5 when g = 8, and at most in general while it is conjectured to be at most . The iterative matching algorithm is also extended for Unrestricted Ring Grooming with arbitrary g, and a loose upper bound on its approximation ratio is . In addition, set-cover based approximation algorithms have been proposed for both Unrestricted Ring Grooming and Restricted
Ring Grooming. They have approximation ratios of at most 1 + log g, but running time in polynomial of m
g
.
Work supported by a DIMACS postdoctoral fellowship. 相似文献
18.
Center and Distinguisher for Strings with Unbounded Alphabet 总被引:2,自引:0,他引:2
Consider two sets
and
of strings of length L with characters from an unbounded alphabet , i.e., the size of is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of
is a string that minimizes the maximum of Hamming1
distance(s, s*) over all string s : s
. In contrast, a farthest string t* from
maximizes the minimum of Hamming distance(t*,t) over all elements t: t
. A distinguisher of
from
is a string that is close to every string in
and far away from any string in
. We obtain polynomial time approximation schemes to settle the above problems. 相似文献
19.
Wun-Tat Chan Yong Zhang Stanley P. Y. Fung Deshi Ye Hong Zhu 《Journal of Combinatorial Optimization》2007,13(3):277-288
We study the problem of finding a longest common increasing subsequence (LCIS) of multiple sequences of numbers. The LCIS
problem is a fundamental issue in various application areas, including the whole genome alignment. In this paper we give an
efficient algorithm to find the LCIS of two sequences in time where n is the length of each sequence andr is the number of ordered pairs of positions at which the two sequences match, ℓ is the length of the LCIS, and Sort(n) is the time to sort n numbers. For m sequences wherem ≥ 3, we find the LCIS in Sort(n)) time where r is the total number of m-tuples of positions at which the m sequences match. The previous results find the LCIS of two sequences in O(n
2) and Sort(n)) time. Our algorithm is faster when r is relatively small, e.g., for . 相似文献
20.
We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular
case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case
with non-unit customers’ demands the exploration of the neighborhood becomes an
-hard problem. 相似文献