Showing 1 to 10 of 2921 matching Articles
Results per page:
By
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
Show all (4)
4 Citations
The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most 1. The question can be considered as a natural variation of the extensively studied Feedback Vertex Set (FVS) problem, where the deletion of at most k vertices has to result in the remaining graph having treewidth at most 1 (i.e., being a forest). Recently Philip et al. (WG, Lecture Notes in Computer Science, vol. 6410, pp. 196–207, 2010) initiated the study of the parameterized complexity of POVD, showing a quartic kernel and an algorithm which runs in time 7^{k}n^{O(1)}. In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65^{k}n^{O(1)}, thus obtaining almost tight kernelization bounds when compared to the general result of Dell and van Melkebeek (STOC, pp. 251–260, ACM, New York, 2010). Techniques used in the kernelization are based on the quadratic kernel for FVS, due to Thomassé (ACM Trans. Algorithms 6(2), 2010).
more …
By
Ďuriš, Pavol; Sýkora, Ondrej; Thompson, Clark D.; Vrto, Imrich
Show all (4)
5 Citations
We prove tight upper and lower bounds on the area of semelective, whenoblivious VLSI circuits for the problem oflselection. The area required to select thelth smallest ofnkbit integers is found to be heavily dependent on the relative sizes ofl,k, andn. Whenl<2^{k}, the minimal area isA = Θ(minn,l(klogl)). Whenl≥2^{k},A = Θ(2^{k}(loglk + 1)).
more …
By
Salzman, Oren; Hemmer, Michael; Raveh, Barak; Halperin, Dan
Show all (4)
5 Citations
We present a general and modular algorithmic framework for path planning of robots. Our framework combines geometric methods for exact and complete analysis of lowdimensional configuration spaces, together with practical, considerably simpler samplingbased approaches that are appropriate for higher dimensions. In order to facilitate the transfer of advanced geometric algorithms into practical use, we suggest taking samples that are entire lowdimensional manifolds of the configuration space that capture the connectivity of the configuration space much better than isolated point samples. Geometric algorithms for analysis of lowdimensional manifolds then provide powerful primitive operations. The modular design of the framework enables independent optimization of each modular component. Indeed, we have developed, implemented and optimized a primitive operation for complete and exact combinatorial analysis of a certain set of manifolds, using arrangements of curves of rational functions and concepts of generic programming. This in turn enabled us to implement our framework for the concrete case of a polygonal robot translating and rotating amidst polygonal obstacles. We show that this instance of the framework is probabilistically complete. Moreover, we demonstrate that the integration of several carefully engineered components leads to significant speedup over the popular PRM samplingbased algorithm, which represents the more simplistic approach that is prevalent in practice.
more …
By
Poon, SheungHung; Shin, ChanSu; Strijk, Tycho; Uno, Takeaki; Wolff, Alexander
Show all (5)
14 Citations
Annotating maps, graphs, and diagrams with pieces of text is an
important step in information visualization that is usually referred
to as label placement. We define nine labelplacement models for
labeling points with axisparallel rectangles given a weight for
each point. There are two groups: fixedposition models and slider
models. We aim to maximize the weight sum of those points that
receive a label.
We first compare our models by giving bounds for the ratios between
the weights of maximumweight labelings in different models. Then
we present algorithms for labeling n points with unitheight
rectangles. We show how an O(n\log n)time factor2 approximation
algorithm and a PTAS for fixedposition models can be extended to
handle the weighted case. Our main contribution is the first
algorithm for weighted sliding labels. Its approximation factor is
(2+\varepsilon), it runs in O(n^{2}/\varepsilon) time and uses
O(n/\varepsilon) space.
We show that other than for fixedposition models even the
projection to one dimension remains NPhard.
For slider models we also investigate some special cases, namely
(a) the number of different point weights is bounded, (b) all labels
are unit squares, and (c) the ratio between maximum and minimum
label height is bounded.
more …
By
Miyazawa, F. K.; Wakabayashi, Y.
30 Citations
The threedimensional packing problem can be stated as follows. Given a list of boxes, each with a given length, width, and height, the problem is to pack these boxes into a rectangular box of fixedsize bottom and unbounded height, so that the height of this packing is minimized. The boxes have to be packed orthogonally and oriented in all three dimensions. We present an approximation algorithm for this problem and show that its asymptotic performance bound is between 2.5 and 2.67. This result answers a question raised by Li and Cheng [5] about the existence of an algorithm for this problem with an asymptotic performance bound less than 2.89.
more …
By
Philip, Geevarghese; Rajan, Varun; Saurabh, Saket; Tale, Prafullkumar
Show all (4)
In the Subset Feedback Vertex Set (SubsetFVS) problem the input is a graph G on n vertices, a subset T of vertices of G called the “terminal” vertices, and an integer k. The task is to determine whether there exists a subset of vertices of cardinality at most k which together intersect all cycles which pass through the terminals. SubsetFVS generalizes several well studied problems including Feedback Vertex Set and Multiway Cut. This problem is known to be NPComplete, even in split graphs. Cygan et al. (SIAM J Discrete Math 27(1):290–309, 2013) proved that SubsetFVS is fixed parameter tractable (
$$\mathsf {FPT}$$
) in general graphs when parameterized by k. In split graphs a simple observation reduces the problem to an equivalent instance of the 3Hitting Set problem with the same solution size. This directly implies, for SubsetFVSrestricted to split graphs, (i) an
$$\mathsf {FPT}$$
algorithm which solves the problem in
$$\mathcal {O}^{\star } (2.076^k)$$
time (The
$$\mathcal {O}^{\star } ()$$
notation hides polynomial factors.) (Wahlström in Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. Thesis, Department of Computer and Information Science, Linköpings universitet, 2007), and (ii) a kernel of size
$$\mathcal {O}(k^3)$$
. We improve both these results for SubsetFVS on split graphs; we derive (i) a kernel of size
$$\mathcal {O}(k^2)$$
which is the best possible unless
$$\textsf {NP}\subseteq {\mathsf {coNP}}/{\textsf {poly}}$$
, and (ii) an algorithm which solves the problem in time
$$\mathcal {O}^*(2^k)$$
. Our algorithm, in fact, solves SubsetFVS on the more general class of chordal graphs, also in
$$\mathcal {O}^*(2^k)$$
time. To the best of our knowledge, the fastest known exact algorithm for SubsetFVS on chordal graphs is based on the 3Hitting Set algorithm of Fomin et al. (JACM 66(2):8, 2019) which runs in
$$\mathcal {O}^*(1.5182^n)$$
time. Applying the results of Fomin et al.
(2019) to our
$$\mathsf {FPT}$$
algorithm yields two exact exponentialtime algorithms for SubsetFVS on chordal graphs: a randomized algorithm which runs in
$$\mathcal {O}^*(1.5^{n})$$
time, and a deterministic algorithm which runs in
$$\mathcal {O}^*((1.5+\varepsilon )^{n})$$
time for any fixed
$$\varepsilon >0$$
.
more …
By
Jaffe, Jeffrey M.; Rosberg, Zvi
We consider an infinite tandem network in which every node is capable of hearing its neighbors up to a given distancen. At any moment of time every node may contain in the top of its queue a message destined to one of its neighbors. This network can be used as a model for a microwave or optic link with many users. For small and largen we investigate the maximal selection of nodes in the network, for which their transmissions are collisionfree. For a large hearing range we show that the upper bound on the maximal selection, which is found herein, is asymptotically achievable. For small hearing ranges we show that a greedy selection is better but not asymptotically optimal. We also specify a sequence of upper bounds which converge to the maximal throughput.
more …
By
King, Valerie; Lewis, Scott; Saia, Jared; Young, Maxwell
Show all (4)
5 Citations
We present two new algorithms, Arc Length and Peer Count, for choosing a peer uniformly at random from the set of all peers in Chord (Proceedings of the ACM SIGCOMM 2001 Technical Conference, 2001). We show analytically that, in expectation, both algorithms have latency O(log n) and send O(log n) messages. Moreover, we show empirically that the average latency and message cost of Arc Length is 10.01log n and that the average latency and message cost of Peer Count is 20.02log n. To the best of our knowledge, these two algorithms are the first fully distributed algorithms for choosing a peer uniformly at random from the set of all peers in a Distributed Hash Table (DHT). Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peertopeer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving faulttolerance.
more …
By
Bilò, Davide; Gualà, Luciano; Proietti, Guido
6 Citations
Given an nnode, undirected and 2edgeconnected graph G=(V,E) with positive real weights on its m edges, given a set of ksource nodes S⊆V, and given a spanning tree T of G, the routing cost fromS of T is the sum of the distances in T from every source s∈S to all the other nodes of G. If an edge e of T undergoes a transient failure, and one needs to promptly reestablish the connectivity, then to reduce setup and rerouting costs it makes sense to temporarily replace e by means of a swap edge, i.e., an edge in G reconnecting the two subtrees of T induced by the removal of e. Then, a best swap edge for e is a swap edge which minimizes the routing cost from S of the tree obtained after the swapping. As a natural extension, the allbest swap edges problem is that of finding a best swap edge for every edge of T, and this has been recently solved in O(mn) time and linear space. In this paper, we focus our attention on the relevant cases in which k=O(1) and k=n, which model realistic communication paradigms. For these cases, we improve the above result by presenting an
$\widetilde{O}(m)$
time and linear space algorithm. Moreover, for the case k=n, we also provide an accurate analysis showing that the obtained swap tree is effective in terms of routing cost. Indeed, if the input tree T has a routing cost from V which is a constantfactor away from that of a minimum routingcost spanning tree (whose computation is a problem known to be in APX), and if in addition nodes in T enjoys a suitable distance stretching property from a tree centroid (which can be constructively induced, as we show), then the tree obtained after the swapping has a routing cost from V which is still a constantratio approximation of that of a new (i.e., in the graph deprived of the failed edge) minimum routingcost spanning tree.
more …
