共查询到20条相似文献,搜索用时 31 毫秒
1.
Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, the power of a node
is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by
applications in wireless networks, we consider several fundamental undirected network design problems under the power minimization
criteria. Given a graph
G=(V,E)\mathcal{G}=(V,\mathcal{E})
with edge costs {c(e):e∈ℰ} and degree requirements {r(v):v∈V}, the
Minimum-Power Edge-Multi-Cover\textsf{Minimum-Power Edge-Multi-Cover}
(MPEMC\textsf{MPEMC}
) problem is to find a minimum-power subgraph G of
G\mathcal{G}
so that the degree of every node v in G is at least r(v). We give an O(log n)-approximation algorithms for
MPEMC\textsf{MPEMC}
, improving the previous ratio O(log 4
n). This is used to derive an O(log n+α)-approximation algorithm for the undirected
$\textsf{Minimum-Power $\textsf{Minimum-Power
($\textsf{MP$\textsf{MP
) problem, where α is the best known ratio for the min-cost variant of the problem. Currently,
_boxclosen-k)\alpha=O(\log k\cdot \log\frac{n}{n-k})
which is O(log k) unless k=n−o(n), and is O(log 2
k)=O(log 2
n) for k=n−o(n). Our result shows that the min-power and the min-cost versions of the
$\textsf{$\textsf{
problem are equivalent with respect to approximation, unless the min-cost variant admits an o(log n)-approximation, which seems to be out of reach at the moment. 相似文献
2.
An axis-parallel k-dimensional box is a Cartesian product R 1×R 2×???×R k where R i (for 1≤i≤k) is a closed interval of the form [a i ,b i ] on the real line. For a graph G, its boxicity box?(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a $\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}An axis-parallel k-dimensional box is a Cartesian product R
1×R
2×⋅⋅⋅×R
k
where R
i
(for 1≤i≤k) is a closed interval of the form [a
i
,b
i
] on the real line. For a graph G, its boxicity box (G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc.
A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs.
For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set
problem for boxicity d graphs, given a box representation, has a
?1+\frac1clogn?d-1\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}
approximation ratio for any constant c≥1 when d≥2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether
the boxicity of a graph is at most 2 itself is NP-hard. 相似文献
3.
We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant 0 < α < 1, we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses log n+O((log n)1-a)\log\, n+O((\log\, n)^{1-\alpha}) random bits to make 7 queries to a proof of size n·2O((log n)1-a)n·2^{O((\log\, n)^{1-\alpha})}, where each query is answered by O((log n)1-a)O((\log\, n)^{1-\alpha}) bit long string, and the verifier has perfect completeness and error 2-W((log n)a)2^{-\Omega((\log\, n)^{\alpha})}. 相似文献
4.
5.
Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs
Given an undirected multigraph G=(V,E), a family $\mathcal{W}Given an undirected multigraph G=(V,E), a family
W\mathcal{W}
of areas W⊆V, and a target connectivity k≥1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between v and W for every pair of a vertex v∈V and an area
W ? WW\in \mathcal{W}
. So far this problem was shown to be NP-complete in the case of k=1 and polynomially solvable in the case of k=2. In this paper, we show that the problem for k≥3 can be solved in O(m+n(k
3+n
2)(p+kn+nlog n)log k+pkn
3log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and
p=|W|p=|\mathcal{W}|
. 相似文献
6.
Thomas Sauerwald 《Algorithmica》2010,56(1):51-88
In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially,
one vertex of a graph G=(V,E) owns a piece of information which is spread iteratively to all other vertices: in each timestep t=1,2,… every informed vertex chooses a neighbor uniformly at random and informs it. The question is how many time steps are required until all
vertices become informed (with high probability).
For various graph classes, involved methods have been developed in order to show an upper bound of
O(logN+diam(G))\mathcal{O}(\log N+\mathop{\mathrm{diam}}(G))
on the runtime of the push-algorithm, where N is the number of vertices and
diam(G)\mathop{\mathrm{diam}}(G)
denotes the diameter of G. However, no asymptotically tight bound on the runtime based on the mixing time of random walks has been established. In
this work we fill this gap by deriving an upper bound of
O(Tmix+logN)\mathcal{O}(\mathsf {T}_{\mathop{\mathrm{mix}}}+\log N)
, where
Tmix\mathsf{T}_{\mathop{\mathrm{mix}}}
denotes the mixing time of a certain random walk on G. After that we prove upper bounds that are based on certain edge expansion properties of G. However, for hypercubes neither the bound based on the mixing time nor the bounds based on edge expansion properties are
tight. That is why we develop a general way to combine these two approaches by which we can deduce that the runtime of the
push-algorithm is Θ(log N) on every Hamming graph. 相似文献
7.
We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem ? is a way, for every possible input I of ?, to provide an “advice” (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem ? can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (?log?n?,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies $t\geq\tilde{\Omega}(\sqrt{n})We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem ℘ is a way, for every possible input I of ℘, to provide an “advice” (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem ℘ can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (⌈log n⌉,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies t 3 [(W)\tilde](?n)t\geq\tilde{\Omega}(\sqrt{n}). Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially
the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of
any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size
of the advices from log n to constant. 相似文献
8.
Huaming Zhang 《Algorithmica》2010,57(2):381-397
We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloorWe study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular
exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations
between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium
on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik,
Freie Universit?t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph
Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph
algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an
example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph
with n vertices in a grid of size bounded by W×H, where
W £ ?\frac2n-23?W\leq\lfloor\frac{2n-2}{3}\rfloor
, and
W+H £ ?\frac4n-43?W+H\leq\lfloor \frac{4n-4}{3}\rfloor
. It uses at most
?\frac2n-53?\lfloor\frac{2n-5}{3}\rfloor
bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline
drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts
in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2). 相似文献
9.
The concept of $(\overline{\in},\overline{\in} \vee \overline{q})The concept of ([`( ? )],[`( ? )] ú[`(q)])(\overline{\in},\overline{\in} \vee \overline{q})-fuzzy interior ideals of semigroups is introduced and some related properties are investigated. In particular, we describe
the relationships among ordinary fuzzy interior ideals, (∈, ∈ ∨ q)-fuzzy interior ideals and ([`( ? )],[`( ? )] ú[`(q)])(\overline{\in},\overline{\in} \vee \overline{q})-fuzzy interior ideals of semigroups. Finally, we give some characterization of [F]
t
by means of (∈, ∈ ∨ q)-fuzzy interior ideals. 相似文献
10.
We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called ε-far from k-vertex-connectivity when at least $\frac{\epsilon dn}{2}$ edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is ε-far from k-vertex-connectivity with a probability of at least 2/3. The algorithm runs in $O(d(\frac{c}{\epsilon d})^{k}\log\frac {1}{\epsilon d})$ time (c>1 is a constant) for (k?1)-vertex-connected graphs, and in $O(d(\frac{ck}{\epsilon d})^{k}\log\frac{k}{\epsilon d})$ time (c>1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k≥4. 相似文献
11.
A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial
time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/log log n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in
the sense that there are caterpillars whose bandwidth is larger than their local density by a factor of Ω(log n/log log n). The previous best approximation ratio for the bandwidth of caterpillars was O(log n). We show that any further improvement in the approximation ratio would require using linear arrangements that do not respect
the order of the vertices of the backbone.
We also show how to obtain a (1+ε) approximation for the bandwidth of caterpillars in time
. This result generalizes to trees, planar graphs, and any family of graphs with treewidth
. 相似文献
12.
Pinar Heggernes Daniel Meister Charis Papadopoulos 《Theoretical computer science》2011,412(39):5466-5486
A graph has linear clique-width at most k if it has a clique-width expression using at most k labels such that every disjoint union operation has an operand which is a single vertex graph. We give the first characterisation of graphs of linear clique-width at most 3, and we give the first polynomial-time recognition algorithm for graphs of linear clique-width at most 3. In addition, we present new characterisations of graphs of linear clique-width at most 2. We also give a layout characterisation of graphs of bounded linear clique-width; a similar characterisation was independently shown by Gurski and by Lozin and Rautenbach. 相似文献
13.
We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes unique. The Isolation Lemma as described in Mulmuley et al. (Combinatorica 7(1):105–131, 1987) achieves the same for general graphs using randomness, whereas we can do it deterministically when restricted to bipartite
planar graphs. As a consequence, we reduce both decision and construction versions of the perfect matching problem in bipartite
planar graphs to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a
highly parallel
SPL\mathsf{SPL}
algorithm for both decision and construction versions of the bipartite perfect matching problem. This improves the earlier
known bounds of non-uniform
SPL\mathsf{SPL}
by Allender et al. (J. Comput. Syst. Sci. 59(2):164–181, 1999) and
NC\mathsf{NC}
2 by Miller and Naor (SIAM J. Comput. 24:1002–1017, 1995), and by Mahajan and Varadarajan (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp.
351–357, 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite
planar graphs, which has been open for a long time. Further we try to find the lower bound on the number of bits needed for
deterministically isolating a perfect matching. We show that our particular method for isolation will require Ω(log n) bits. Our techniques are elementary. 相似文献
14.
Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number
of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority
of these algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase
selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two-phased
algorithms, the relation between the independence number α and the connected domination number γ
c
of a unit-disk graph plays the key role. The best-known relation between them is
a £ 3\frac23gc+1\alpha\leq3\frac{2}{3}\gamma_{c}+1. In this paper, we prove that α≤3.4306γ
c
+4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed
in the literature. 相似文献
15.
A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4. 相似文献
16.
Roel Verstappen 《Journal of scientific computing》2011,49(1):94-110
Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that
the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us
to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore,
in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales
of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is
needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size
smaller than Δ initially. From this we deduce that the eddy viscosity ν
e
has to depend on the invariants
q = \frac12tr(S2)q = \frac{1}{2}\mathrm{tr}(S^{2}) and
r = -\frac13tr(S3)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by
ne = \frac32(D/p)2 |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re
τ
=590). 相似文献
17.
We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an $O(2^{6.903\sqrt{n}})We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our
approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined
techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach
we show how to obtain an
O(26.903?n)O(2^{6.903\sqrt{n}})
time algorithm solving weighted Hamiltonian Cycle on an n-vertex planar graph. Similar technique solves Planar Graph Travelling Salesman Problem with n cities in time
O(29.8594?n)O(2^{9.8594\sqrt{n}})
. Our approach can be used to design parameterized algorithms as well. For example, we give an algorithm that for a given
k decides if a planar graph on n vertices has a cycle of length at least k in time
O(213.6?kn+n3)O(2^{13.6\sqrt{k}}n+n^{3})
. 相似文献
18.
Binh-Minh Bui-Xuan Jan Arne Telle Martin Vatshelle 《Theoretical computer science》2011,412(39):5187-5204
We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods-Boolean sums of neighborhoods-across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n2k22k) and Minimum Weight Dominating Set in time O(n2+nk23k). With an additional n2 factor in the runtime, we can also count all independent sets and dominating sets of each cardinality.Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n2) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n). 相似文献
19.
Vicky Choi 《Quantum Information Processing》2011,10(3):343-353
In Choi (Quantum Inf Process, 7:193–209, 2008), we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design
problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate
an optimal complete-graph-minor hardware graph. Given a family F{\mathcal{F}} of graphs, a (host) graph U is called F{\mathcal{F}}-minor-universal if for each graph G in F, U{\mathcal{F}, U} contains a minor-embedding of G. The problem for designing a F{{\mathcal{F}}}-minor-universal hardware graph U
sparse
in which F{{\mathcal{F}}} consists of a family of sparse graphs (e.g., bounded degree graphs) is open. 相似文献
20.
Romeo Rizzi 《Algorithmica》2009,53(3):402-424
In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of
scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle
bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis
of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C
i
in
such that
is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying
WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature.
Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In
this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be
-hard. However, in this paper, we also offer a simple and practical 2⌈log 2
n⌉-approximation algorithm for the MWFCB problem. In O(n
ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log 2
n⌉∑
e∈E(G)
w
e
, thus allowing a fast 2⌈log 2
n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB. 相似文献