共查询到20条相似文献,搜索用时 15 毫秒
1.
We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d i ) i=1 n with maximum degree d max?=O(m 1/4?τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md max?) where $m=\frac{1}{2}\sum_{i}d_{i}We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence
in a certain range. For degree sequence (d
i
)
i=1
n
with maximum degree d
max =O(m
1/4−τ
), our algorithm generates almost uniform random graphs with that degree sequence in time O(md
max ) where
m=\frac12?idim=\frac{1}{2}\sum_{i}d_{i}
is the number of edges in the graph and τ is any positive constant. The fastest known algorithm for uniform generation of these graphs (McKay and Wormald in J. Algorithms
11(1):52–67, 1990) has a running time of O(m
2
d
max 2). Our method also gives an independent proof of McKay’s estimate (McKay in Ars Combinatoria A 19:15–25, 1985) for the number of such graphs. 相似文献
2.
Sebastian Dörn 《Theory of Computing Systems》2009,45(3):613-628
We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges:
Our quantum algorithms are faster than the best known classical deterministic algorithms for the corresponding problems.
In particular, the second result solves an open question stated in a paper by Ambainis and Špalek (Proceedings of STACS’06,
pp. 172–183, 2006). 相似文献
• | Finding a maximal matching in general graphs in time . |
• | Finding a maximum matching in general graphs in time . |
• | Finding a maximum weight matching in bipartite graphs in time , where N is the largest edge weight. |
3.
Abstract. A proper coloring of the edges of a graph G is called acyclic if there is no two-colored cycle in G . The acyclic edge chromatic number of G , denoted by a'(G) , is the least number of colors in an acyclic edge coloring of G . For certain graphs G , a'(G)\geq Δ(G)+2 where Δ(G) is the maximum degree in G . It is known that a'(G)≤ Δ + 2 for almost all Δ -regular graphs, including all Δ -regular graphs whose girth is at least cΔ log Δ . We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem. For graphs
G with sufficiently large girth in terms of Δ(G) , we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Δ(G)+2 colors. 相似文献
4.
We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication)
in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full
knowledge about the size and the topology of the network. We show that gossiping can be completed in
time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than
units of time. Moreover, we show a
schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules
by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log 3
n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log 2
n) time broadcasting schedule by Kowalski and Pelc.
A preliminary version of this paper appeared in the proceedings of ISAAC’06.
F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported
by the Research Council of Norway through the SPECTRUM project. 相似文献
5.
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. 相似文献
6.
Joel Ratsaby 《Annals of Mathematics and Artificial Intelligence》2008,52(1):55-65
Consider a class of binary functions h: X→{ − 1, + 1} on an interval . Define the sample width of h on a finite subset (a sample) S ⊂ X as ω
S
(h) = min
x ∈ S
|ω
h
(x)| where ω
h
(x) = h(x) max {a ≥ 0: h(z) = h(x), x − a ≤ z ≤ x + a}. Let be the space of all samples in X of cardinality ℓ and consider sets of wide samples, i.e., hypersets which are defined as Through an application of the Sauer-Shelah result on the density of sets an upper estimate is obtained on the growth function
(or trace) of the class , β > 0, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples
of cardinality m. The estimate is .
相似文献
7.
During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering
even the most basic network coordination problems difficult. Before any reasonable communication can take place, nodes must
come up with an initial structure that can serve as a foundation for more sophisticated algorithms. In this paper, we consider
the problem of obtaining a vertex coloring as such an initial structure. We propose an algorithm that works in the unstructured
radio network model. This model captures the characteristics of newly deployed ad hoc and sensor networks, i.e. asynchronous
wake-up, no collision-detection, and scarce knowledge about the network topology. When modeling the network as a graph with
bounded independence, our algorithm produces a correct coloring with O(Δ) colors in time O(Δ log n) with high probability, where n and Δ are the number of nodes in the network and the maximum degree, respectively. Also, the number of locally used colors depends
only on the local node density. Graphs with bounded independence generalize unit disk graphs as well as many other well-known
models for wireless multi-hop networks. They allow us to capture aspects such as obstacles, fading, or irregular signal-propagation.
A preliminary version of this work has been published in [20] as Coloring Unstructured Radio Networks, In Proceedings of the 17th Symposium on Parallel Algorithms and Architectures (SPAA), Las Vegas, Nevada, 2005. 相似文献
8.
Michel Barbeau Prosenjit Bose Paz Carmi Mathieu Couture Evangelos Kranakis 《Algorithmica》2011,60(2):236-249
We present the first location-oblivious distributed unit disk graph coloring algorithm having a provable performance ratio
of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This
is an improvement over the standard sequential coloring algorithm that has a worst case lower bound on its performance ratio
of 4−3/k (for any k>2, where k is the chromatic number of the unit disk graph achieving the lower bound) (Tsai et al., in Inf. Process. Lett. 84(4):195–199,
2002). We present a slightly better worst case lower bound on the performance ratio of the sequential coloring algorithm for unit
disk graphs with chromatic number 4. Using simulation, we compare our algorithm with other existing unit disk graph coloring
algorithms. 相似文献
9.
We give a linear-time recognition algorithm for circular-arc graphs based on the algorithm of Eschen and Spinrad (Proceedings
of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 128–137, 1993) and Eschen (PhD thesis, 1997). Our algorithm both improves the time bound of Eschen and Spinrad, and fixes some flaws in it. Our algorithm is simpler
than the earlier linear-time recognition algorithm of McConnell (Algorithmica 37(2):93–147, 2003), which is the only linear time recognition algorithm previously known. 相似文献
10.
Eric Allender David A. Mix Barrington Tanmoy Chakraborty Samir Datta Sambuddha Roy 《Theory of Computing Systems》2009,45(4):675-723
We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for
. In particular, we focus on different classes of planar graphs, of which grid graphs are an important special case. Our main results are:
E. Allender supported in part by NSF Grant CCF-0514155.
D.A. Mix Barrington supported in part by NSF Grant CCR-9988260.
S. Roy supported in part by NSF Grant CCF-0514155. 相似文献
• | Reachability in graphs of genus one is logspace-equivalent to reachability in grid graphs (and in particular it is logspace-equivalent to both reachability and non-reachability in planar graphs). |
• | Many of the natural restrictions on grid-graph reachability (GGR) are equivalent under reductions (for instance, undirected GGR, outdegree-one GGR, and indegree-one-outdegree-one GGR are all equivalent). These problems are all equivalent to the problem of determining whether a completed game position in HEX is a winning position, as well as to the problem of reachability in mazes studied by Blum and Kozen (IEEE Symposium on Foundations of Computer Science (FOCS), pp. 132–142, [1978]). These problems provide natural examples of problems that are hard for under reductions but are not known to be hard for ; they thus give insight into the structure of . |
• | Reachability in layered planar graphs is logspace-equivalent to layered grid graph reachability (LGGR). We show that LGGR lies in (a subclass of ). |
• | Series-Parallel digraphs (on which reachability was shown to be decidable in logspace by Jakoby et al.) are a special case of single-source-single-sink planar directed acyclic graphs (DAGs); reachability for such graphs logspace reduces to single-source-single-sink acyclic grid graphs. We show that reachability on such grid graphs reduces to undirected GGR. |
• | We build on this to show that reachability for single-source multiple-sink planar DAGs is solvable in . |
11.
In this paper we introduce a minimax model unifying several classes of single facility planar center location problems. We
assume that the transportation costs of the demand points to the serving facility are convex functions {Q
i
}, i=1,…,n, of the planar distance used. Moreover, these functions, when properly transformed, give rise to piecewise quadratic functions
of the coordinates of the facility location. In the continuous case, using results on LP-type models by Clarkson (J. ACM 42:488–499,
1995), Matoušek et al. (Algorithmica 16:498–516, 1996), and the derandomization technique in Chazelle and Matoušek (J. Algorithms 21:579–597, 1996), we claim that the model is solvable deterministically in linear time. We also show that in the separable case, one can
get a direct O(nlog n) deterministic algorithm, based on Dyer (Proceedings of the 8th ACM Symposium on Computational Geometry, 1992), to find an optimal solution. In the discrete case, where the location of the center (server) is restricted to some prespecified
finite set, we introduce deterministic subquadratic algorithms based on the general parametric approach of Megiddo (J. ACM
30:852–865, 1983), and on properties of upper envelopes of collections of quadratic arcs. We apply our methods to solve and improve the complexity
of a number of other location problems in the literature, and solve some new models in linear or subquadratic time complexity. 相似文献
12.
Stanley P. Y. Fung Feifeng Zheng Wun-Tat Chan Francis Y. L. Chin Chung Keung Poon Prudence W. H. Wong 《Journal of Scheduling》2008,11(4):299-308
We study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted
throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same
length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous
algorithm of (Kim, J.-H., Chwa, K.-Y. in Theor. Comput. Sci. 325(3):479–488, 2004) which is shown to be 5-competitive by (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218,
2004). In the case that pages may have different lengths, we give a (
)-competitive algorithm where Δ is the ratio of maximum to minimum page lengths. This improves the (4Δ+3)-competitive algorithm
of (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). We also prove an almost matching lower bound of Ω(Δ/log Δ). Furthermore, for small values of Δ we give better lower bounds.
The work described in this paper was fully supported by grants from the Research Grants Council of the Hong Kong SAR, China
[CityU 1198/03E, HKU 7142/03E, HKU 5172/03E], an NSF Grant of China [No. 10371094], and a Nuffield Foundation Grant of UK
[NAL/01004/G]. 相似文献
13.
We consider a model of game-theoretic network design initially studied by Anshelevich et al. (Proceedings of the 45th Annual
Symposium on Foundations of Computer Science (FOCS), pp. 295–304, 2004), where selfish players select paths in a network to minimize their cost, which is prescribed by Shapley cost shares. If
all players are identical, the cost share incurred by a player for an edge in its path is the fixed cost of the edge divided
by the number of players using it. In this special case, Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations
of Computer Science (FOCS), pp. 295–304, 2004) proved that pure-strategy Nash equilibria always exist and that the price of stability—the ratio between the cost of the
best Nash equilibrium and that of an optimal solution—is Θ(log k), where k is the number of players. Little was known about the existence of equilibria or the price of stability in the general weighted version of the game. Here, each player i has a weight w
i
≥1, and its cost share of an edge in its path equals w
i
times the edge cost, divided by the total weight of the players using the edge.
This paper presents the first general results on weighted Shapley network design games. First, we give a simple example with
no pure-strategy Nash equilibrium. This motivates considering the price of stability with respect to α-approximate Nash equilibria—outcomes from which no player can decrease its cost by more than an α multiplicative factor. Our first positive result is that O(log w
max )-approximate Nash equilibria exist in all weighted Shapley network design games, where w
max is the maximum player weight. More generally, we establish the following trade-off between the two objectives of good stability
and low cost: for every α=Ω(log w
max ), the price of stability with respect to O(α)-approximate Nash equilibria is O((log W)/α), where W is the sum of the players’ weights. In particular, there is always an O(log W)-approximate Nash equilibrium with cost within a constant factor of optimal.
Finally, we show that this trade-off curve is nearly optimal: we construct a family of networks without o(log w
max / log log w
max )-approximate Nash equilibria, and show that for all α=Ω(log w
max /log log w
max ), achieving a price of stability of O(log W/α) requires relaxing equilibrium constraints by an Ω(α) factor.
Research of H.-L. Chen supported in part by NSF Award 0323766.
Research of T. Roughgarden supported in part by ONR grant N00014-04-1-0725, DARPA grant W911NF-04-9-0001, and an NSF CAREER
Award. 相似文献
14.
Martin Hoefer 《Algorithmica》2009,53(1):104-131
In this paper we consider the connection game, a simple network design game with independent selfish agents that was introduced by Anshelevich et al. (Proc. 35th Ann.
ACM Symp. Theo. Comp. (STOC), pp. 511–520, 2003). Our study concerns an important subclass of tree games, in which every feasible network is guaranteed to be connected. It generalizes the class of single-source games considered
by Anshelevich et al. We focus on the existence, quality, and computability of pure-strategy exact and approximate Nash equilibria.
For tree connection games, in which every player holds two terminals, we show that there is a Nash equilibrium as cheap as
the optimum network. In contrast, for single-source games, in which every player has at most three terminals, the price of
stability is at least k−2, and it is
-complete to decide the existence of a Nash equilibrium. Hence, we propose polynomial time algorithms for computing approximate
Nash equilibria, which provide relaxed stability and cost efficiency guarantees. For the case of two terminals per player,
there is an algorithm to find a (2+ε,1.55)-approximate Nash equilibrium. It can be generalized to an algorithm to find a (3.1+ε,1.55)-approximate Nash equilibrium for general tree connection games. This improves the guarantee of the only previous algorithm
for the problem, which returns a (4.65+ε,1.55)-approximate Nash equilibrium. Tightness results for the analysis of all algorithms are derived. Our algorithms use
a novel iteration technique for trees that might be of independent interest.
This work has appeared in part as an extended abstract at the 31st Symposium on Mathematical Foundations of Computer Science
(MFCS 2006) and the 17th International Symposium on Algorithms and Computation (ISAAC 2006).
Supported by DFG Research Training Group 1042 “Explorative Analysis and Visualization of Large Information Spaces”. 相似文献
15.
This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication)
in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed in advance based
on full knowledge about the size and the topology of the network. The first part of the paper examines the two communication
primitives in arbitrary graphs. In particular, for the broadcast task we deliver two new results: a deterministic efficient
algorithm for computing a radio schedule of length D + O(log3
n), and a randomized algorithm for computing a radio schedule of length D + O(log2
n). These results improve on the best currently known D + O(log4
n) time schedule due to Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231,
2005). Later we propose a new (efficiently computable) deterministic schedule that uses 2D + Δlog n + O(log3
n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time
, for any network with the diameter D = Ω(log
i+4
n), where i is an arbitrary integer constant i ≥ 0, see Gąsieniec et al. (Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity,
vol. 3104, pp. 173–184, 2004). The second part of the paper focuses on radio communication in planar graphs, devising a new
broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on the currently best known D + O(log3
n) time schedule proposed by Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231,
2005). Our new algorithm should be also seen as a separation result between planar and general graphs with small diameter
due to the polylogarithmic inapproximability result for general graphs by Elkin and Kortsarz (Proceedings of the 7th International
Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 3122, pp. 105–116, 2004; J. Algorithms
52(1), 8–25, 2004).
The second author is supported in part by a grant from the Israel Science Foundation and by the Royal Academy of Engineering.
Part of this research was performed while this author (Q. Xin) was a PhD student at The University of Liverpool. 相似文献
16.
Iwona Cieślik 《Acta Informatica》2005,42(1):1-20
The problem of on-line coloring of an arbitrary graphs is known to be hard. Here we consider the problem of on-line coloring
in the simplified situation where the input graph is KKs,t-free. We show that the on-line coloring algorithm with the First Fit strategy of proposed by Capponi and Pilotto in [1] is the best one for KK1,t-free graphs (t≥3). A.Capponi and C.Pilotto have shown that this algorithm achieves a competitive ratio of t−1 while we show that it is the best possible. However for the family of KKs,t-free graphs (s≥2, t≥2) there exists no on-line coloring algorithm with a competitive function. The problem of an on-line cliques covering for
these families is hard. There exists no on-line cliques covering algorithm with a competitive function for the family of KKs,t-free graphs (s≥ 1, t≥3). The additional assumption that the input graph is given in a connected way does not help a lot and does not change our
results described above. 相似文献
17.
Takeaki Uno 《Algorithmica》2010,56(1):3-16
The problem of finding dense structures in a given graph is quite basic in informatics including data mining and data engineering.
Clique is a popular model to represent dense structures, and widely used because of its simplicity and ease in handling. Pseudo
cliques are natural extension of cliques which are subgraphs obtained by removing small number of edges from cliques. We here
define a pseudo clique by a subgraph such that the ratio of the number of its edges compared to that of the clique with the
same number of vertices is no less than a given threshold value. In this paper, we address the problem of enumerating all
pseudo cliques for a given graph and a threshold value. We first show that it seems to be difficult to obtain polynomial time
algorithms using straightforward divide and conquer approaches. Then, we propose a polynomial time, polynomial delay in precise,
algorithm based on reverse search. The time complexity for each pseudo clique is O(Δlog |V|+min {Δ
2,|V|+|E|}). Computational experiments show the efficiency of our algorithm for both randomly generated graphs and practical graphs. 相似文献
18.
Timothy M. Chan 《Algorithmica》2008,50(2):236-243
We describe an O(n
3/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (SIAM J. Comput. 5:49–60,
1976), Takaoka (Inform. Process. Lett. 43:195–199, 1992), Dobosiewicz (Int. J. Comput. Math. 32:49–60, 1990), Han (Inform. Process. Lett. 91:245–250, 2004), Takaoka (Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, pp. 278–289, Springer, 2004), and Zwick (Proc. 15th Int. Sympos. Algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, pp. 921–932, Springer,
2004). The new algorithm is surprisingly simple and different from previous ones.
A preliminary version of this paper appeared in Proc. 9th Workshop Algorithms Data Struct. (WADS), Lect. Notes Comput. Sci.,
vol. 3608, pp. 318–324, Springer, 2005. 相似文献
19.
Jean Frédéric Myoupo Aboubecrine Ould Cheikhna Idrissa Sow 《The Journal of supercomputing》2010,52(2):135-148
The Distributed Mobility-Adaptive Clustering (DMAC) due to Basagni partitions the nodes of a mobile ad hoc network into clusters,
thus giving the network a hierarchical organization. This algorithm supports the mobility of the nodes, even during the cluster
formation. The main feature of DMAC is that in a weighted network (in which two or more nodes cannot have the same weight),
nodes have to choose the clusterheads taking into account only the node weight, i.e. the mobility when a node weight is the
inverse of its speed. In our approach many nodes may have the same speed and hence the same weight. We assume that nodes have
no identities and the number of nodes, say n, is the only known parameter of the network. After the randomized clustering, we show that the initialization problem can
be solved in a multi-hop ad hoc wireless network of n stations in O(k
1/2log 1/2
k)+D
b
−1+O(log (max (P
i
)+log 2max (P
i
)) broadcast rounds with high probability, where k is the number of clusters, D
b
is the blocking diameter and max (P
i
), 1≤i≤k, is the maximum number of nodes in a cluster. Thus the initialization protocol presented here uses less broadcast rounds
than the one in Ravelemanana (IEEE Trans. Parallel Distributed Syst. 18(1):17–28 2007). 相似文献
20.
Tak-Wah Lam Lap-Kei Lee Isaac K. K. To Prudence W. H. Wong 《Journal of Scheduling》2012,15(1):105-116
Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between
flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805–813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409–420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647–659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called
CRR (classified round robin) on m≥2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result
still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis
that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size. 相似文献