共查询到20条相似文献,搜索用时 187 毫秒
1.
The Orbit problem is defined as follows: Given a matrix A∈ℚ
n×n
and vectors x,y∈ℚ
n
, does there exist a non-negative integer i such that A
i
x=y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4):808–821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for
C=L with respect to logspace many-one reductions. 相似文献
2.
For a permutation f of the vertex set V(G) of a connected graph G, let δ
f
(x,y)=|d(x,y)−d(f(x),f(y))|. Define the displacement δ
f
(G) of G with respect to f to be the sum of δ
f
(x,y) over all unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ
f
(G) among the n! permutations f of V(G). In this note, we determine all trees T with π(T)=2 or 4.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
For a positive integer k, a total {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0,1,2,…,k} such that for any vertex v∈V(G), the condition ∑
u∈N(v)
f(u)≥k is fulfilled, where N(v) is the open neighborhood of v. A set {f
1,f
2,…,f
d
} of total {k}-dominating functions on G with the property that ?i=1dfi(v) £ k\sum_{i=1}^{d}f_{i}(v)\le k for each v∈V(G), is called a total {k}-dominating family (of functions) on G. The maximum number of functions in a total {k}-dominating family on G is the total {k}-domatic number of G, denoted by dt{k}(G)d_{t}^{\{k\}}(G). Note that dt{1}(G)d_{t}^{\{1\}}(G) is the classic total domatic number d
t
(G). In this paper we initiate the study of the total {k}-domatic number in graphs and we present some bounds for dt{k}(G)d_{t}^{\{k\}}(G). Many of the known bounds of d
t
(G) are immediate consequences of our results. 相似文献
6.
We study the problem of separating sublinear time computations via approximating the diameter for a sequence S=p
1
p
2
⋅⋅⋅
p
n
of points in a metric space, in which any two consecutive points have the same distance. The computation is considered respectively
under deterministic, zero error randomized, and bounded error randomized models. We obtain a class of separations using various
versions of the approximate diameter problem based on restrictions on input data. We derive tight sublinear time separations
for each of the three computation models via proving that computation with O(n
r
) time is strictly more powerful than that with O(n
r−ε
) time, where r and ε are arbitrary parameters in (0,1) and (0,r) respectively. We show that, for any parameter r∈(0,1), the bounded error randomized sublinear time computation in time O(n
r
) cannot be simulated by any zero error randomized sublinear time algorithm in o(n) time or queries; and the same is true for zero error randomized computation versus deterministic computation. 相似文献
7.
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 maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γpr(G). We establish bounds on Γpr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γpr(G)≤4n/5 if δ=1 and n≥3, Γpr(G)≤3n/4 if δ=2 and n≥6, and Γpr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γpr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γpr(G)=3n/4 are characterized. 相似文献
8.
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. 相似文献
9.
Haoli Wang Xirong Xu Yuansheng Yang Kai Lü 《Journal of Combinatorial Optimization》2011,21(4):481-496
Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k
-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k
-distance paired domination number, denoted by γ
p
k
(G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1. 相似文献
10.
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ
r
(G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show
that if G is a cubic graph of order n, then
gr(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4}
, and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then
gr(G) £ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}.
Lastly, we show that if G is a claw-free cubic graph, then γ
r
(G)=γ(G). 相似文献
11.
A set S of vertices in a graph G=(V,E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted by γ
tr
(G), is the minimum cardinality of a TRDS of G. In this paper we characterize the claw-free graphs G of order n with γ
tr
(G)=n. Also, we show that γ
tr
(G)≤n−Δ+1 if G is a connected claw-free graph of order n≥4 with maximum degree Δ≤n−2 and minimum degree at least 2 and characterize those graphs which achieve this bound. 相似文献
12.
Given an acyclic digraph D, the competition graph C(D) of D is the graph with the same vertex set as D and two distinct vertices x and y are adjacent in C(D) if and only if there is a vertex v in D such that (x,v) and (y,v) are arcs of D. The competition number κ(G) of a graph G is the least number of isolated vertices that must be added to G to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly two
holes is at most three. 相似文献
13.
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊂eqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of G−S at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ
m
, and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r
k
(G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r
k
(G,γ
m
) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r
k
(G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r
k
(G,ddom) < 3n/4 + 2k/7. These bounds are sharp.
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
14.
Let A be a non-trivial Abelian group. A graph G=(V,E) is A-magic if there exists a labeling f:E→A∖{0} such that the induced vertex set labeling f
+:V→A, defined by f
+(v)=∑f(uv) where the sum is over all uv∈E, is a constant map. The integer-magic spectrum of a graph G is the set IM(G)={k∈ℕ∣G is ℤ
k
-magic}. A sun graph is obtained from an n-cycle, by attaching paths to each pair of adjacent vertices in the cycle. In this paper, we investigate the integer-magic
spectra of some sun graphs.
Dedicated to Prof. Frank K. Hwang, on the occasion of his 65th birthday.
Supported by Faculty Research Grant, Hong Kong Baptist University. 相似文献
15.
Changcun Ma Donghyun Kim Yuexuan Wang Wei Wang Nassim Sohaee Weili Wu 《Journal of Combinatorial Optimization》2010,20(3):249-258
Given a k-connected graph G=(V,E) and V
′⊂V, k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find S⊂V∖V
′ with minimum cardinality such that the subgraph induced by V
′∪S is k-connected. In this paper, we study the hardness of k-VCSAP in undirect graphs. We first prove k-VCSAP is APX-hard. Then, we improve the lower bound in two ways by relying on different assumptions. That is, we prove no
algorithm for k-VCSAP has a PR better than O(log (log n)) unless P=NP and O(log n) unless NP⊆DTIME(n
O(log log n)), where n is the size of an input graph. 相似文献
16.
Suppose G is a graph of p vertices. A proper labeling
f of G is a one-to-one mapping f:V(G)→{1,2,…,p}. The cyclic bandwidth sum of
G
with respect to
f is defined by CBS
f
(G)=∑
uv∈E(G)|f(v)−f(u)|
p
, where |x|
p
=min {|x|,p−|x|}. The cyclic bandwidth sum of G is defined by CBS(G)=min {CBS
f
(G): f is a proper labeling of G}. The bandwidth sum of
G
with respect to
f is defined by BS
f
(G)=∑
uv∈E(G)|f(v)−f(u)|. The bandwidth sum of G is defined by BS(G)=min {BS
f
(G): f is a proper labeling of G}. In this paper, we give a necessary and sufficient condition for BS(G)=CBS(G), and use this to show that BS(T)=CBS(T) when T is a tree. We also find cyclic bandwidth sums of complete bipartite graphs.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
Supported in part by the National Science Council under grants NSC91-2115-M-156-001. 相似文献
17.
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. 相似文献
18.
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. 相似文献
19.
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. 相似文献
20.
This paper examines inference on regressions when interval data are available on one variable, the other variables being measured precisely. Let a population be characterized by a distribution P(y, x, v, v0, v1), where y∈R1, x∈Rk, and the real variables (v, v0, v1) satisfy v0≤v≤v1. Let a random sample be drawn from P and the realizations of (y, x, v0, v1) be observed, but not those of v. The problem of interest may be to infer E(y|x, v) or E(v|x). This analysis maintains Interval (I), Monotonicity (M), and Mean Independence (MI) assumptions: (I) P(v0≤v≤v1)=1; (M) E(y|x, v) is monotone in v; (MI) E(y|x, v, v0, v1)=E(y|x, v). No restrictions are imposed on the distribution of the unobserved values of v within the observed intervals [v0, v1]. It is found that the IMMI Assumptions alone imply simple nonparametric bounds on E(y|x, v) and E(v|x). These assumptions invoked when y is binary and combined with a semiparametric binary regression model yield an identification region for the parameters that may be estimated consistently by a modified maximum score (MMS) method. The IMMI assumptions combined with a parametric model for E(y|x, v) or E(v|x) yield an identification region that may be estimated consistently by a modified minimum‐distance (MMD) method. Monte Carlo methods are used to characterize the finite‐sample performance of these estimators. Empirical case studies are performed using interval wealth data in the Health and Retirement Study and interval income data in the Current Population Survey. 相似文献