共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
对于给定的距离参数。,性质测试算法A需以高概率正确地区分给定的对象具备预定性质II与二远离性质
II。若存在II的测试算法A满足其询问复杂性独立于规模参数n,则称II是可测的。设H是一个图,性质仔了)℃。为
不含井子图的图所构成的集合。在有界度模型中,Goldreich与Ron证明了对任意连通图H,性质仔力℃。是可测
的}s}。在邻接矩阵模型中,证明了对任意图H,不管其连通与否,性质件厂re。是可测的。 相似文献
3.
Symmetry is one of the most important aesthetic criteria in graph
drawing because it reveals the structure in the graph. This paper
discusses symmetric drawings of biconnected planar graphs. More
specifically, we discuss geometric automorphisms, that is,
automorphisms of a graph G that can be represented as symmetries
of a drawing of G. Finding geometric automorphisms is the first
and most difficult step in constructing symmetric drawings of
graphs. The problem of determining whether a given graph has a
non-trivial geometric automorphism is NP-complete for general
graphs. In this paper we present a linear time algorithm for
finding planar geometric automorphisms of biconnected planar
graphs. A drawing algorithm is also discussed. 相似文献
4.
5.
Symmetry is one of the most important aesthetic criteria in graph
drawing because it reveals structure in the graph. This paper
discusses symmetric drawings of oneconnected planar graphs.
More specifically, we discuss planar (geometric)
automorphisms, that is, automorphisms of a graph G that can be
represented as symmetries of a planar drawing of G. Finding
planar automorphisms is the first and most difficult step in
constructing planar symmetric drawings of graphs. The problem of
determining whether a given graph has a nontrivial geometric
automorphism is NP-complete for general graphs. The two previous papers in this series have discussed the problem
of drawing planar graphs with a maximum number of symmetries, for
the restricted cases where the graph is triconnected and
biconnected. This paper extends the previous results to cover
planar graphs that are oneconnected. We present a linear
time algorithm for drawing oneconnected planar graphs with a
maximum number of symmetries. 相似文献
6.
We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows: where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.
相似文献
$$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$
7.
8.
9.
Maximum G Edge-Packing (EPack
G
) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H . This paper investigates the computational complexity of edge-packing for planar guests and planar hosts. Edge-packing is
solvable in polynomial time when both G and H are trees. Edge-packing is solvable in linear time when H is outerplanar and G is either a 3-cycle or a k -star (a graph isomorphic to K
1,k
). Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with edges. A strategy for developing polynomial-time approximation algorithms for planar hosts is exemplified by a linear-time
approximation algorithm that finds a k -star edge-packing of size at least half the optimal.
Received May 1995, and in revised form November 1995, and in final form December 1997. 相似文献
10.
Abstract. We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding
a heaviest planar subgraph in an edge-weighted graph G . This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM
WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3 , which is obtained by any algorithm that produces a maximum weight spanning tree in G . Based on the Berman—Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3+1/72 and at most 5/12 . We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8 . Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2 ) for the NP-hard SC MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem. 相似文献
11.
12.
Given a planar graph $G=(V,E)$ and a rooted forest ${\FF}=(V_{\FF}, A_{\FF})$
with leaf set $V$, we wish to decide whether $G$ has a plane embedding $\GG$
satisfying the following condition: There are $|V_{\FF}|-|V|$ pairwise noncrossing
Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of
${\FF}$ such that for every nonleaf vertex $f$ of ${\FF}$, the interior of the curve
$\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\FF}$
but contains no other leaves of ${\FF}$.
This problem arises from theoretical studies in geographic database systems.
It is unknown whether this problem can be solved in polynomial time.
This paper presents an almost linear-time algorithm for a nontrivial special case
where the set of leaf descendants of each nonleaf vertex $f$ in ${\FF}$ induces
a connected subgraph of $G$. 相似文献
13.
We study several embeddings of doubling metrics into low dimensional normed spaces, in particular into ? 2 and ? ∞ . Doubling metrics are a robust class of metric spaces that have low intrinsic dimension, and often occur in applications. Understanding the dimension required for a concise representation of such metrics is a fundamental open problem in the area of metric embedding. Here we show that the n-vertex Laakso graph can be embedded into constant dimensional ? 2 with the best possible distortion, which has implications for possible approaches to the above problem. 相似文献
14.
We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G . This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3 , which is obtained by any algorithm that produces a maximum weight spanning tree in G . Based on the Berman—Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3+1/72 and at most 5/12 . We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8 . Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2 ) for the NP-hard SC MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem. 相似文献
15.
Sergio Cabello 《Algorithmica》2012,62(1-2):361-381
We show how to compute in O(n 4/3log?1/3 n+n 2/3 k 2/3log?n) time the distance between k given pairs of vertices of a planar graph G with n vertices. This improves previous results whenever (n/log?n)5/6≤k≤n 2/log?6 n. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs. 相似文献
16.
In this paper, we consider the problem of representing planar graphs by polygons whose sides touch. We show that at least
six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also
show that the lower bound of six sides is matched by an upper bound of six sides with a linear-time algorithm for representing
any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges having at most three slopes
and with all vertices lying on an O(n)×O(n) grid. 相似文献
17.
We consider graphs whose vertices may be in one of two different states: either on or off . We wish to maintain dynamically such graphs under an intermixed sequence of updates and queries. An update may reverse
the status of a vertex, by switching it either on or off , and may insert a new edge or delete an existing edge. A query tests whether any two given vertices are connected in the
subgraph induced by the vertices that are on . We give efficient algorithms that maintain information about connectivity on planar graphs in O( log
3
n) amortized time per query, insert, delete, switch-on, and switch-off operation over sequences of at least Ω(n) operations, where n is the number of vertices of the graph.
Received September 1997; revised January 1999. 相似文献
18.
Lukasz Kowalik 《Algorithmica》2010,58(3):770-789
Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n 2) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is $\mathcal{O}(n\log n)Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Gr?tzsch’s
theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n
2) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is
O(nlogn)\mathcal{O}(n\log n)
. 相似文献
19.
Isolde Adler Frederic Dorn Fedor V. Fomin Ignasi Sau Dimitrios M. Thilikos 《Algorithmica》2012,64(1):69-84
Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is an edge of H, then there is an edge of G between components C u and C v . A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming. 相似文献
20.
An independent set of a graph is a set of vertices without edges
between them. Every planar graph has an independent set of size at
least (1/4)n and there are planar graphs for which any
independent set has size at most (1/4)n.
In this paper similar bounds are provided for the problem of
bounded-degree independent set, i.e., an independent set where
additionally all vertices have degree less than a pre-specified bound
D. Our upper and lower bounds match (up to a small constant) for
D 16. 相似文献