共查询到20条相似文献,搜索用时 31 毫秒
1.
Teresa W. Haynes Michael A. Henning Lucas C. van der Merwe 《Journal of Combinatorial Optimization》2009,18(1):23-37
Let G be a graph and
be the complement of G. The complementary prism
of G is the graph formed from the disjoint union of G and
by adding the edges of a perfect matching between the corresponding vertices of G and
. For example, if G is a 5-cycle, then
is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any
graph G,
and
, where γ(G) and γ
t
(G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds.
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
2.
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). 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
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 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
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. 相似文献
10.
Yoshiyuki Kusakari Daisuke Masubuchi Takao Nishizeki 《Journal of Combinatorial Optimization》2001,5(2):249-266
Let G = (V,E) be a plane graph with nonnegative edge weights, and let
be a family of k vertex sets
, called nets. Then a noncrossing Steiner forest for
in G is a set
of k trees
in G such that each tree
connects all vertices, called terminals, in net N
i, any two trees in
do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time
if G has n vertices and each net contains a bounded number of terminals. 相似文献
11.
Hans L. Bodlaender 《Journal of Combinatorial Optimization》2003,7(3):283-290
A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth. 相似文献
12.
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. 相似文献
13.
Abdo Y. Alfakih Tongnyoul Yi Katta G. Murty 《Journal of Combinatorial Optimization》2000,4(3):365-388
We show that the problem of finding a perfect matching satisfying a single equality constraint with a 0–1 coefficients in an n × n incomplete bipartite graph, polynomially reduces to a special case of the same peoblem called the partitioned case. Finding a solution matching for the partitioned case in the incomlpete bipartite graph, is equivalent to minimizing a partial sum of the variables over
= the convex hull of incidence vectors of solution matchings for the partitioned case in the complete bipartite graph. An important strategy to solve this minimization problem is to develop a polyhedral characterization of
. Towards this effort, we present two large classes of valid inequalities for
, which are proved to be facet inducing using a facet lifting scheme. 相似文献
14.
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. 相似文献
15.
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). 相似文献
16.
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. 相似文献
17.
Online scheduling on parallel machines with two GoS levels 总被引:2,自引:0,他引:2
Yiwei Jiang 《Journal of Combinatorial Optimization》2008,16(1):28-38
This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests
from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled
with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less
than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels.
It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound
of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio
.
Research supported by Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in Proceedings
of AAIM2006, LNCS, 4041, 11-21. 相似文献
18.
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
. 相似文献
19.
The 2-INTERVAL PATTERN problem is to find the largest constrained pattern in a set of 2-intervals. The constrained pattern
is a subset of the given 2-intervals such that any pair of them are R-comparable, where model . The problem stems from the study of general representation of RNA secondary structures. In this paper, we give three improved
algorithms for different models. Firstly, an O(n{log} n +L) algorithm is proposed for the case , where is the total length of all 2-intervals (density d is the maximum number of 2-intervals over any point). This improves previous O(n
2log n) algorithm. Secondly, we use dynamic programming techniques to obtain an O(nlog n + dn) algorithm for the case R = { <, ⊏ }, which improves previous O(n
2) result. Finally, we present another algorithm for the case with disjoint support(interval ground set), which improves previous O(n
2□n) upper bound.
A preliminary version of this article appears in Proceedings of the 16th Annual International Symposium on Algorithms and
Computation, Springer LNCS, Vol. 3827, pp. 412–421, Hainan, China, December 19–21, 2005. 相似文献
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. 相似文献