共查询到20条相似文献,搜索用时 46 毫秒
1.
Chung-Haw Chang Chao-Ming Sun Hua-Min Huang Lih-Hsing Hsu 《Journal of Combinatorial Optimization》2007,14(2-3):349-364
Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C
k
(u,v). A k-container is a k
*-container if it spans all vertices of G. We define G to be a k
*-laceable graph if there is a k
*-container joining any two vertices from different partite sets. A k
*-container C
k
*(u,v)={P
1,…,P
k
} is equitable if ||V(P
i
)|−|V(P
j
)||≤2 for all 1≤i,j≤k. A graph is equitably k
*-laceable if there is an equitable k
*-container joining any two vertices in different partite sets. Let Q
n
be the n-dimensional hypercube. In this paper, we prove that the hypercube Q
n
is equitably k
*-laceable for all k≤n−4 and n≥5.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013. 相似文献
2.
Ming Liu Chengbin Chu Yinfeng Xu Jiazhen Huo 《Journal of Combinatorial Optimization》2012,23(2):189-195
We study the online problem of single machine scheduling to minimize total general completion time. General completion time
is defined as Caj=(Cj)aC^{\alpha}_{j}=(C_{j})^{\alpha}, where C
j
denotes the completion time of job J
j
and α≥1 is a constant integer. Total general completion time characterizes the feather in service that when a customer is served
later in time, his dissatisfaction increases in a manner of power function. The objective function ∑(C
j
)
α
can also be viewed as a total weighted completion time, but the “weight” is no longer a constant number. Our purpose to minimize
customers’ total dissatisfaction. The problem is online in the sense that all jobs arrive over time. Each job’s processing
time becomes known at its arrival time. Preemption is not allowed. For this online problem, we show that a lower bound on
competitive ratio is 2
α
and prove that D-SPT (delayed shortest processing time) algorithm is optimal with a competitive ratio 2
α
. 相似文献
3.
Peter Che Bor Lam Wensong Lin Jianzhuan Wu 《Journal of Combinatorial Optimization》2007,14(2-3):219-227
Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ
j,k
-number of G, denoted by λ
j,k
(G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)|
m
≥j if u and v are adjacent; and |f(u)−f(v)|
m
≥k if u and v are at distance two apart, where |x|
m
=min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ
j,k
-number of G and denoted by σ
j,k
(G). The λ
j,k
-numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ
j,k
-numbers of direct products of two complete graphs and the σ
j,k
-numbers of direct products and Cartesian products of two complete graphs.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast
University Science Foundation grant XJ0607230. 相似文献
4.
Hanno Lefmann 《Journal of Combinatorial Optimization》2008,16(2):182-195
In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]2 are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n
6k−4) time algorithm is given, which finds distributions of n points in [0,1]2 such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)1/(j−2)/n
(j−1)/(j−2)). 相似文献
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.
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). 相似文献
7.
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. 相似文献
8.
The following planar minimum disk cover problem is considered in this paper: given a set
D\mathcal{D}
of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum
cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within
a factor of (1+ε) in
O(mnO(\frac1e2log2\frac1e))\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})})
time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover
problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several
variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem
are considered and approximation schemes are designed. 相似文献
9.
Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ+, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted
version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen
these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the
set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm
for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within
a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time. 相似文献
10.
Adrian Kosowski Michał Małafiejski Paweł Żyliński 《Journal of Combinatorial Optimization》2007,14(1):63-86
Given an undirected, connected graph G with maximum degree Δ, we introduce the concept of a [1, Δ]-factor k-packing in G, defined as a set of k edge-disjoint subgraphs of G such that every vertex of G has an incident edge in at least one subgraph. The problem of deciding whether a graph admits a [1,Δ]-factor k-packing is shown to be solvable in linear time for k = 2, but NP-complete for all k≥ 3. For k = 2, the optimisation problem of minimising the total number of edges of the subgraphs of the packing is NP-hard even when
restricted to subcubic planar graphs, but can in general be approximated within a factor of by reduction to the Maximum 2-Edge-Colorable Subgraph problem. Finally, we discuss implications of the obtained results for
the problem of fault-tolerant guarding of a grid, which provides the main motivation for research. 相似文献
11.
We study the online rectangle filling problem which arises in channel aware scheduling of wireless networks, and present deterministic
and randomized results for algorithms that are allowed a k-lookahead for k≥2. Our main result is a deterministic min {1.848,1+2/(k−1)}-competitive online algorithm. This is the first algorithm for this problem with a competitive ratio approaching 1 as
k approaches +∞. The previous best-known solution for this problem has a competitive ratio of 2 for any k≥2. We also present a randomized online algorithm with a competitive ratio of 1+1/(k+1). Our final result is a closely matching lower bound (also proved in this paper) of
$1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2))$1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2))
on the competitive ratio of any randomized online algorithm against an oblivious adversary. These are the first known results
for randomized algorithms for this problem. 相似文献
12.
Khaled Elbassioni Kazuhisa Makino Imran Rauf 《Journal of Combinatorial Optimization》2011,22(3):293-304
Golumbic et al. (Discrete Appl. Math. 154:1465–1477, 2006) defined the readability of a monotone Boolean function f to be the minimum integer k such that there exists an ∧−∨-formula equivalent to f in which each variable appears at most k times. They asked whether there exists a polynomial-time algorithm, which given a monotone Boolean function f, in CNF or DNF form, checks whether f is a read-k function, for a fixed k. In this paper, we partially answer this question already for k=2 by showing that it is NP-hard to decide if a given monotone formula represents a read-twice function. It follows also from
our reduction that it is NP-hard to approximate the readability of a given monotone Boolean function f:{0,1}
n
→{0,1} within a factor of
O(n)\mathcal{O}(n)
. We also give tight sublinear upper bounds on the readability of a monotone Boolean function given in CNF (or DNF) form,
parameterized by the number of terms in the CNF and the maximum size in each term, or more generally the maximum number of
variables in the intersection of any constant number of terms. When the variables of the DNF can be ordered so that each term
consists of a set of consecutive variables, we give much tighter logarithmic bounds on the readability. 相似文献
13.
Lü Damei 《Journal of Combinatorial Optimization》2013,26(2):385-392
For two positive integers j and k with j≥k, an L(j,k)-labeling of a graph G is an assignment of nonnegative integers to V(G) such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(2,1)-labelings-number of the edge-path-replacement G(P k ) of a graph G. Note that G(P 3) is the incidence graph of G. L(2,1)-labelings of the edge-path-replacement G(P 3) of a graph, called (2,1)-total labeling of G, was introduced by Havet and Yu in 2002 (Workshop graphs and algorithms, Dijon, France, 2003; Discrete Math. 308:498–513, 2008). They (Havet and Yu, Discrete Math. 308:498–513, 2008) obtain the bound $\Delta+1\leq\lambda^{T}_{2}(G)\leq2\Delta+1$ and conjectured $\lambda^{T}_{2}(G)\leq\Delta+3$ . In this paper, we obtain that λ(G(P k ))≤Δ+2 for k≥5, and conjecture λ(G(P 4))≤Δ+2 for any graph G with maximum degree Δ. 相似文献
14.
Finding an anti-risk path between two nodes in undirected graphs 总被引:1,自引:0,他引:1
Given a weighted graph G=(V,E) with a source s and a destination t, a traveler has to go from s to t. However, some of the edges may be blocked at certain times, and the traveler only observes that upon reaching an adjacent
site of the blocked edge. Let ℘={P
G
(s,t)} be the set of all paths from s to t. The risk of a path is defined as the longest travel under the assumption that any edge of the path may be blocked. The paper
will propose the Anti-risk Path Problem of finding a path P
G
(s,t) in ℘ such that it has minimum risk. We will show that this problem can be solved in O(mn+n
2log n) time suppose that at most one edge may be blocked, where n and m denote the number of vertices and edges in G, respectively.
This research is supported by NSF of China under Grants 70525004, 60736027, 70121001 and Postdoctoral Science Foundation of
China under Grant 20060401003. 相似文献
15.
Jun Guo 《Journal of Combinatorial Optimization》2010,19(4):492-500
Let
\mathbbF(2n+d)q2\mathbb{F}^{(2\nu+\delta)}_{q^{2}}
be a (2ν+δ)-dimensional unitary space of
\mathbbFq2\mathbb{F}_{q^{2}}
, where δ=0 or 1. In this paper we construct a family of inclusion matrices associated with subspaces of
\mathbbF(2n+d)q2\mathbb{F}^{(2\nu+\delta)}_{q^{2}}
, and exhibit its disjunct property. Moreover, we compare the ratio efficiency of this construction with others, and find
it smaller under some conditions. 相似文献
16.
Zengti Li Suogang Gao Hongjie Du Feng Zou Weili Wu 《Journal of Combinatorial Optimization》2010,20(4):325-334
In this paper, we construct two classes of t×n,s
e
-disjunct matrix with subspaces in orthogonal space
\mathbbFq(2n+1)\mathbb{F}_{q}^{(2\nu+1)}
of characteristic 2 and exhibit their disjunct properties. We also prove that the test efficiency t/n of constructions II is smaller than that of D’yachkov et al. (J. Comput. Biol. 12:1129–1136, 2005). 相似文献
17.
Rocchio’s similarity-based relevance feedback algorithm, one of the most important query reformation methods in information
retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio’s algorithm often
uses a fixed query updating factor. When this is the case, we strengthen the linear Ω(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61–86, 2002) and prove that Rocchio’s algorithm makes Ω(k(n−k)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1}
n
, when the inner product similarity measure is used. A quadratic lower bound is obtained when k is linearly proportional to n. We also prove an O(k(n−k)3) upper bound for Rocchio’s algorithm with the inner product similarity measure in searching for such a collection of documents
with a constant query updating factor and a zero classification threshold. 相似文献
18.
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. 相似文献
19.
Tung-Yang Ho Chun-Nan Hung Lih-Hsing Hsu 《Journal of Combinatorial Optimization》2007,14(2-3):275-294
A graph G=(V,E) is Hamiltonian connected if there exists a Hamiltonian path between any two vertices in G. Let P
1=(u
1,u
2,…,u
|V|) and P
2=(v
1,v
2,…,v
|V|) be any two Hamiltonian paths of G. We say that P
1 and P
2 are independent if u
1=v
1,u
|V|=v
|V|, and u
i
≠v
i
for 1<i<|V|. A cubic graph G is 2-independent Hamiltonian connected if there are two independent Hamiltonian paths between any two different vertices of G. A graph G is 1-Hamiltonian if G−F is Hamiltonian for any F⊆V∪E with |F|=1. A graph G is super 3*-connected if there exist i internal disjoint paths spanning G for i=1,2,3. It is proved that every super 3*-connected graph is 1-Hamiltonian. In this paper, we prove that every cubic 2-independent Hamiltonian connected graph is also
1-Hamiltonian. We present some cubic 2-independent Hamiltonian connected graphs that are super 3*-connected, some cubic 2-independent Hamiltonian connected graphs that are not super 3*-connected, some super 3*-connected graphs that are not 2-independent Hamiltonian connected, and some cubic 1-Hamiltonian graphs that are Hamiltonian
connected but neither 2-independent Hamiltonian connected nor super 3*-connected.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
This work was supported in part by the National Science Council of the Republic of China under Contract NSC 94-2213-E-233-011. 相似文献
20.
The problem of partitioning a partially ordered set into a minimum number of chains is a well-known problem. In this paper
we study a generalization of this problem, where we not only assume that the chains have bounded size, but also that a weight
w
i
is given for each element i in the partial order such that w
i
≤w
j
if i
≺
j. The problem is then to partition the partial order into a minimum-weight set of chains of bounded size, where the weight
of a chain equals the weight of the heaviest element in the chain. We prove that this problem is
-hard, and we propose and analyze lower bounds for this problem. Based on these lower bounds, we exhibit a 2-approximation
algorithm, and show that it is tight. We report computational results for a number of real-world and randomly generated problem
instances. 相似文献