共查询到20条相似文献,搜索用时 46 毫秒
1.
2.
《Journal of Computer and System Sciences》2016,82(6):1044-1063
We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph with edge-weights and vertex-weights are given. The goal is to find a vertex set with while minimizing , where is the total weight of the edges with exactly one endpoint in S and . For this problem, we present a factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when . We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems. 相似文献
3.
4.
Let be a connected graph on n vertices. The proximity of G is the minimum average distance from a vertex of G to all others. The eccentricity of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity of the graph G is . Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on vertices, , with equality if and only if . In this paper, we show that this conjecture is true. 相似文献
5.
6.
7.
8.
9.
《Journal of Computer and System Sciences》2016,82(5):782-792
This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset of depots that i can potentially select from and use. When for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an -time algorithm. For the restricted 1-median problem, we give an -time algorithm. For the unrestricted 1-median problem, we give an -time algorithm. 相似文献
10.
11.
12.
Raphael Yuster 《Information Processing Letters》2011,111(21-22):1057-1061
We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in , it runs in time where is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ? in time. 相似文献
13.
《Journal of Computer and System Sciences》2016,82(5):793-801
14.
Jesse Kamp Anup Rao Salil Vadhan David Zuckerman 《Journal of Computer and System Sciences》2011,77(1):191-220
We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on as sources generated by width branching programs. Specifically, there is a constant such that for any , our algorithm extracts bits that are exponentially close to uniform (in variation distance) from space s sources with min-entropy δn, where . Previously, nothing was known for , even for space 0. Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of r independent smaller sources over , where the total min-entropy over all the smaller sources is k. We give deterministic extractors for such sources when k is as small as , for small enough ?. 相似文献
15.
16.
17.
Ito (1976, 1978) [14], [17] provided representations of strongly connected automata by group-matrix type automata. This shows the close connection between strongly connected automata with their automorphism groups. In this paper we deal with commutative asynchronous automata. In particular, we introduce and study normal commutative asynchronous automata and cyclic commutative asynchronous automata. Some properties on endomorphism monoids of these automata are given. Also, the representations of normal commutative asynchronous automata and cyclic commutative asynchronous automata are provided by S-automata and regular S-automata, respectively. The cartesian composition of a strongly connected automaton A and a cyclic commutative asynchronous automaton B is studied. It is shown that the endomorphism monoid of automaton is a Clifford monoid. Finally, a representation of is provided by regular Clifford monoid matrix-type automaton. This generalizes and extends the representations of strongly connected automata given by Ito (1976) [14]. 相似文献
18.
19.