共查询到20条相似文献,搜索用时 31 毫秒
1.
Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating
set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the
model of random unit disk graphs constructed from n random points in an
square. We show that if
and
then for both versions of Rule k, the expected size of the Rule k dominating set is
as
It follows that, for
in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum. 相似文献
2.
The unit ball random geometric graph
has as its vertices n points distributed independently and uniformly in the unit ball in
, with two vertices adjacent if and only if their ℓp-distance is at most λ. Like its cousin the Erdos-Renyi random graph, G has a connectivity threshold: an asymptotic value
for λ in terms of n, above which G is connected and below which G is disconnected. In the connected zone we determine upper
and lower bounds for the graph diameter of G. Specifically, almost always,
, where
is the ℓp-diameter of the unit ball B. We employ a combination of methods from probabilistic combinatorics and stochastic geometry. 相似文献
3.
We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings
on a grid of size
The parameter
depends on the Schnyder wood used for the drawing. This parameter is in the range
The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most
The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular
Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs.
The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing
of a random triangulation is close to
For a random 3-connected plane graph, tests show that the expected size of the drawing is
相似文献
4.
We present a new algorithm to compute motorcycle graphs. It runs in
time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon.
For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton
computation to a motorcycle graph computation in expected
time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n
vertices, among which r are reflex vertices, in
expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in
expected time. 相似文献
5.
Unambiguity in alternating Turing machines has received considerable attention in the context of analyzing globally unique
games by Aida et al. [ACRW] and in the design of efficient protocols involving globally unique games by Crasmaru et al. [CGRS].
This paper explores the power of unambiguity in alternating Turing machines in the following settings: 1. We show that unambiguity-based
hierarchies-AUPH, UPH, and UPH-are infinite in some relativized world. For each
, we construct another relativized world where the unambiguity-based hierarchies collapse so that they have exactly k distinct
levels and their k-th levels coincide with PSPACE. These results shed light on the relativized power of the unambiguity-based
hierarchies, and parallel the results known for the case of the polynomial hierarchy. 2. For every
, we define the bounded-level unambiguous alternating solution class UAS(k) as the class of all sets L for which there exists
a polynomial-time alternating Turing machine N, which need not be unambiguous on every input, with at most k alternations
such that
if and only if x is accepted unambiguously by N. We construct a relativized world where, for all
and
. 3. Finally, we show that robustly k-level unambiguous alternating polynomial-time Turing machines, i.e., polynomial-time
alternating Turing machines that for every oracle have k alternating levels and are unambiguous, accept languages that are
computable in
, for every oracle A. This generalizes a result of Hartmanis and Hemachandra [HH]. 相似文献
6.
We show that for arbitrary positive integers
with probability
the gcd of two linear combinations of these integers with rather small random integer coefficients coincides with
This naturally leads to a probabilistic algorithm for computing the gcd of several integers, with probability
via just one gcd of two numbers with about the same size as the initial data (namely the above linear combinations). This
algorithm can be repeated to achieve any desired confidence level. 相似文献
7.
We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line
of research, we assume that the maximum
demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily
over the graph. Our results are:
We obtain an
approximation ratio for UFP, where n is the number of vertices,
is the maximum degree, and
is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm
gives an
approximation.
For certain strong constant-degree expanders considered by we obtain an
approximation for the uniform capacity case.
For UFP on the line and the ring, we give the first constant-factor approximation algorithms.
All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either
improve upon or
are incomparable with previously known results for these problems. The main technique used for these results is randomized
rounding followed by greedy alteration, and is inspired by the use of this idea in recent work. 相似文献
8.
For a set of rooted, unordered, distinctly leaf-labeled trees, the NP-hard maximum agreement subtree problem (MAST) asks for
a tree contained (up to isomorphism or homeomorphism) in all of the input trees with as many labeled leaves as possible. We
study the ordered variants of MAST where the trees are uniformly or non-uniformly ordered. We provide the first known polynomial-time
algorithms for the uniformly and non-uniformly ordered homeomorphic variants as well as the uniformly and non-uniformly ordered
isomorphic variants of MAST.
Our algorithms run in time
,
,
, and
, respectively, where n is the number of leaf labels and k is
the number of input trees. 相似文献
9.
Klaus Meer 《Theory of Computing Systems》2007,41(1):107-118
In [10] it was recently shown that
that is the existence of transparent long proofs for
was established. The latter denotes the class of real number decision problems verifiable in polynomial time as introduced
by Blum et al. [6]. The present paper is devoted to the question what impact a potential full real number
theorem
would have on approximation issues in the BSS model of computation. We study two natural optimization problems in the BSS
model. The first, denoted by MAX-QPS, is related to polynomial systems; the other, MAX-q-CAP, deals with algebraic circuits.
Our main results combine the PCP framework over
with approximation issues for these two problems. We also give a negative approximation result for a variant of the MAX-QPS
problem. 相似文献
10.
Celina M.H. de Figueiredo Guilherme D. da Fonseca Vinicius G.P. de Sa Jeremy Spinrad 《Algorithmica》2006,46(2):149-180
A homogeneous set is a non-trivial module of a graph, i.e. a non-empty,
non-unitary, proper subset of a graph's vertices such that all its elements
present exactly the same outer neighborhood. Given two graphs
the Homogeneous Set Sandwich Problem (HSSP) asks whether there
exists a sandwich graph
which
has a homogeneous set. In 2001 Tang et al. published
an all-fast
algorithm which was recently proven wrong, so that the HSSP's known upper bound would have been reset
thereafter at the former
determined by Cerioli et al. in 1998. We present, notwithstanding, new deterministic
algorithms which have it established at
We give as
well two even faster
randomized algorithms, whose simplicity might
lend them didactic usefulness. We believe that, besides providing efficient
easy-to-implement procedures to solve it, the study of these new approaches
allows a fairly thorough understanding of the problem. 相似文献
11.
Martin Ziegler 《Theory of Computing Systems》2007,41(1):177-206
By the sometimes so-called Main Theorem of Recursive Analysis, every computable real function is necessarily continuous. We
wonder whether and which kinds of hypercomputation allow for the effective evaluation of also discontinuous
. More precisely the present work considers the following three super-Turing notions of real function computability: - relativized
computation; specifically given oracle access to the Halting Problem
or its jump
; - encoding input
and/or output y = f(x) in weaker ways also related to the Arithmetic Hierarchy; - nondeterministic computation. It turns
out that any
computable in the first or second sense is still necessarily continuous whereas the third type of hypercomputation provides
the required power to evaluate for instance the discontinuous Heaviside function. 相似文献
12.
We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in
terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations.
We construct a quite optimal quantum algorithm for this problem whose complexity is in
. The algorithm uses and highlights the power of the quantization method of
Szegedy. For the lower bound of
, we give a reduction from a special case of Element Distinctness to our problem. Along the way, we prove the optimality of
the algorithm of Pak for the randomized model. 相似文献
13.
Amitabha Bagchi Ankur Bhargava Amitabh Chaudhary David Eppstein Christian Scheideler 《Theory of Computing Systems》2006,39(6):903-928
We study the problem of how resilient networks are to node faults. Specifically, we investigate the question of how many faults
a network can sustain and still contain a large (i.e., linear-sized) connected component with approximately the same expansion
as the original fault-free network. We use a pruning technique that culls away those parts of the faulty network that have
poor expansion. The faults may occur at random or be caused by an adversary. Our techniques apply in either case. In the adversarial
setting we prove that for every network with expansion
a large connected component with basically the same expansion as the original network exists for up to a constant times
faults. We show this result is tight in the sense that every graph G of size n and uniform expansion
can be broken into components of size o(n) with
faults. Unlike the adversarial case, the expansion of a graph gives a very weak bound on its resilience to random faults.
While it is the case, as before, that there are networks of uniform expansion
that are not resilient against a fault probability of a constant times
it is also observed that there are networks of uniform expansion
that are resilient against a constant fault probability. Thus, we introduce a different parameter, called the span of a
graph, which gives us a more precise handle on the maximum fault probability. We use the span to show the first known results
for the effect of random faults on the expansion of d-dimensional meshes. 相似文献
14.
Erik D. Demaine Martin L. Demaine Arthur Langerman Stefan Langerman 《Theory of Computing Systems》2006,39(3):439-453
We study a popular pencil-and-paper game called morpion solitaire. We present upper and lower bounds for the maximum score
attainable for many versions of the game. We also show that, in its most general form, the game is NP-hard and the high score
is inapproximable within
for any
unless P = NP. 相似文献
15.
The increased availability of data describing biological interactions provides important clues on how complex chains of genes
and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures
such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures
are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find
an optimal path structure in
time and
space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number
of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure.
Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity
is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures,
we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures
with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity
by applying it to protein interaction networks in the DIP database. 相似文献
16.
Lane A. Hemaspaandra Mitsunori Ogihara Mohammed J. Zaki Marius Zimand 《Theory of Computing Systems》2006,39(5):669-684
We identify two properties that for P-selective sets are effectively computable. Namely, we show that, for any P-selective
set, finding a string that is in a given length's top Toda equivalence class (very informally put, a string from
that the set's P-selector function declares to be most likely to belong to the set) is
computable, and we show that each P-selective set contains a weakly-
-rankable subset. 相似文献
17.
This paper examines a number of variants of the sparse k-spanner problem and presents hardness results concerning their approximability.
Previously, it was known that most k-spanner problems are weakly inapproximable (namely, they are NP-hard to approximate with
ratio O(log n), for every k ≥ 2) and that the unit-length k-spanner problem for constant stretch requirement k ≥ 5 is strongly
inapproximable (namely, it is NP-hard to approximate with ratio
). The results of this paper significantly expand the ranges of hardness for k-spanner problems. In general, strong hardness
is shown for a number of k-spanner problems, for certain ranges of the stretch requirement k depending on the particular variant
at hand. The problems studied differ by the types of edge weights and lengths used, and they include directed, augmentation
and client-server variants. The paper also considers k-spanner problems in which the stretch requirement k is relaxed (e.g.,
. For these cases, no inapproximability results were known (even for a constant approximation ratio) for any spanner problem.
Moreover, some versions of the k-spanner problem are known to enjoy the ratio-degradation property; namely, their complexity
decreases exponentially with the inverse of the stretch requirement. So far, no hardness result existed precluding any k-spanner
problem from enjoying this property. This paper establishes strong inapproximability results for the case of relaxed stretch
requirement (up to
, for any
), for a large variety of k-spanner problems. It is also shown that these problems do not enjoy the ratio-degradation property. 相似文献
18.
We give a new proof of recent results of Grolmusz and Tardos on the computing power of constant-depth circuits consisting
of a single layer of
gates followed by a fixed number of layers of
-gates, where p is prime. 相似文献
19.
Graph homomorphism, also called H-coloring, is a natural generalization of graph coloring: There is a
homomorphism from a graph G to a complete graph on k vertices if and only if G is k-colorable. During recent years the topic
of exact (exponential-time) algorithms for NP-hard problems in general, and for graph coloring in particular, has led to
extensive research. Consequently, it is natural to ask how the techniques developed for exact graph coloring algorithms can
be extended to graph homomorphisms. By the celebrated result of Hell and Nesetril, for each fixed simple graph H, deciding
whether a given simple graph G has a homomorphism to H is polynomial-time solvable if
H is a bipartite graph, and NP-complete otherwise. The case where H is the cycle of length 5, is the first NP-hard case different
from graph coloring. We show that for an odd integer
, whether an input graph G with n vertices is homomorphic to the cycle of length k, can be decided in time
. We extend the results obtained for cycles, which are graphs of treewidth two, to graphs of bounded treewidth as follows:
if H is of treewidth at most t, then whether input graph G with n vertices is homomorphic to H can be decided in time
. 相似文献
20.
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G
have non-negative weights assigned to them. In this problem a {-1,0,1} incidence vector is associated with each cycle and
the vector space over
generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for
its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. This
paper presents an
algorithm, which is the first polynomial-time algorithm for computing a minimum cycle basis in G. We then improve it to
an
algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied. In this problem
a {0,1} incidence vector is associated with each cycle and the vector space over
generated by these vectors is the cycle space of the graph. There are directed graphs in which the minimum cycle basis has
lower weight than any cycle basis of the underlying undirected graph. Hence algorithms for computing a minimum cycle basis
in an undirected graph cannot be used as black boxes to solve the problem in directed graphs. 相似文献