共查询到20条相似文献,搜索用时 15 毫秒
1.
Journal of Combinatorial Optimization - Let $$G=(V(G),E(G))$$ be a connected graph. A set of vertices $$S\subseteq V(G)$$ is an edge metric generator of G if any pair of edges in G can be... 相似文献
2.
Journal of Combinatorial Optimization - In a graph $$G = (V,E)$$ , a set $$S\subseteq V(G)$$ is said to be a dominating set of G if every vertex not in S is adjacent to a vertex in S. Let G[S]... 相似文献
3.
Dan Jia-Xiong Zhu Zhi-Bo Yang Xin-Kui Li Ru-Yi Zhao Wei-Jie Li Xiang-Jun 《Journal of Combinatorial Optimization》2022,44(1):435-445
Journal of Combinatorial Optimization - A signed edge-domination of graph G is a function $$f:\ E(G)\rightarrow \{+1,-1\}$$ such that $$\sum _{e'\in N_{G}[e]}{f(e')}\ge 1$$ for each $$e\in... 相似文献
4.
Zhang Wanping Meng Jixiang Wu Baoyindureng 《Journal of Combinatorial Optimization》2022,44(2):1199-1220
Journal of Combinatorial Optimization - For $$k \in {\mathbb {N}},$$ Ali et al. (Discrete Appl Math 160:1845-1850, 2012) introduce the Steiner k-Wiener index $$SW_{k}(G)=\sum _{S\in V(G)} d(S),$$... 相似文献
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.
Journal of Combinatorial Optimization - An injective k-coloring of a graph G is a k-coloring c (not necessarily proper) such that $$c(u)\ne c(v)$$ whenever u, v has a common neighbor in G. The... 相似文献
7.
Ito Takehiro Mizuta Haruka Nishimura Naomi Suzuki Akira 《Journal of Combinatorial Optimization》2022,43(5):1264-1279
Journal of Combinatorial Optimization - Suppose that we are given an independent set $$I_0$$ of a graph G, and an integer $$l\ge 0$$ . Then, we are asked to find an independent set of G having the... 相似文献
8.
Dettlaff Magda Gözüpek Didem Raczek Joanna 《Journal of Combinatorial Optimization》2022,44(2):921-933
Journal of Combinatorial Optimization - Given a graph $$G=(V(G), E(G))$$ , the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are... 相似文献
9.
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. 相似文献
10.
Let D = (V, A) be a directed graph, for each vertex v V, let +(v) and – (v) denote the sets of arcs leaving and entering v,
and
be intersecting families on +(v) and –(v), respectively, and
and
be submodular functions on intersecting pairs. A flow f : A R is feasible if
Given a cost function c on A, the minimum cost polymatroidal flow problem is to find a feasible flow f with minimum cost {c(e)f(e)ve A}, it is a significant generalization of many combinatorial optimization problems.Given a feasible flow f*, cost and restriction functions on A, the inverse polymatroidal flow problem is to modify c, optimally and with bounds, such that f* becomes a minimum cost polymatroidal flow under the modified cost.It is shown in this paper that the inverse 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 efficiently by strongly polynomial combinatorial algorithms. We also give a necessary and sufficient condition for the feasibility of the inverse problem. 相似文献
11.
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. 相似文献
12.
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. 相似文献
13.
Journal of Combinatorial Optimization - The Angular Constrained Minimum Spanning Tree Problem ( $$\alpha $$ -MSTP) is defined in terms of a complete undirected graph $$G=(V,E)$$ and an angle... 相似文献
14.
Journal of Combinatorial Optimization - Given $$\lambda >0$$ , an undirected complete graph $$G=(V,E)$$ with nonnegative edge-weight function obeying the triangle inequality and a depot... 相似文献
15.
Journal of Combinatorial Optimization - Let $$\Gamma =\Gamma (V, E)$$ be a simple (multiple edges and loops are not considered), connected (every pair of distinct vertices are joined by a path),... 相似文献
16.
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. 相似文献
17.
This paper studies the on-line production order scheduling problem where each preemption causes a penalty, and the objective
is to maximize the net profit, i.e., the total weights of completed orders minus the total penalties caused by preemptions.
Two greedy strategies are shown to be at best and -competitive respectively, where Δ is the ratio between the longest and shortest length of order. After that we mainly present
an improved strategy, named WAL, which takes advantage of the knowledge of Δ and is proved to be -competitive for Δ > 9. Furthermore, two lower bounds for deterministic strategies, and 6.33, are given for the cases of nonuniform and uniform length respectively.
This research is supported by NSF of China under Grants 70471035, 70525004, 70121001 and 70602031. 相似文献
18.
Journal of Combinatorial Optimization - Given a graph $$G = (V,E)$$ , a vertex $$u \in V$$ ve-dominates all edges incident to any vertex of $$N_G[u]$$ . A set $$S \subseteq V$$ is a ve-dominating... 相似文献
19.
M. Y. Chan Danny Z. Chen Francis Y. L. Chin Cao An Wang 《Journal of Combinatorial Optimization》2006,11(4):435-443
This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given point
set V of size n in the k-dimensional space (k-D) for k = 2,3. The NNE-graph provides another way of connecting points in a communication network, which has lower expected degree
at each point and shorter total length of connections with respect to those using Delaunay triangulation. In fact, the NNE-graph
can also be used as a tool to test whether a point set is randomly generated or has some particular properties.
We show that in 2-D the NNE-graph can be constructed in optimal
time in the worst case. We also present an
time algorithm, where d is the
-th largest degree in the utput NNE-graph. The algorithm is optimal when
. The algorithm is also sensitive to the structure of the NNE-graph, for instance when
, the number of edges in NNE-graph is bounded by
for any value g with
. We finally propose an
time algorithm for the problem in 3-D, where d and
are the
-th largest vertex degree and the largest vertex degree in the NNE-graph, respectively. The algorithm is optimal when the
largest vertex degree of the NNE-graph
is
. 相似文献
20.
We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One
of them is for directed graphs and its approximation ratio is . The other is for undirected graphs and its approximation ratio is . Both algorithms improve on the previous bests.
A preliminary version of this paper appeared in the Proceedings of 13th European Symposium on Algorithms (ESA2005), Lecture
Notes in Computer Science, Vol. 3669, pp. 179–190, 2005. 相似文献