We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).

We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, called sinks, all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm.

Evacuation in emergency situations can be modeled by a dynamic flow network. Two criteria have been used before: one is the evacuation completion time and the other is the aggregate evacuation time of individual evacuees. The aim of this paper is to optimize the aggregate evacuation time in the simplest case, where the network is a path and only one evacuation center (called a sink) is to be introduced. The evacuees are initially located at the vertices, but their precise numbers are unknown, and are given by upper and lower bounds. Under this assumption, we compute the sink location that minimizes the maximum "regret." We present an $O(n^2\log n)$ time algorithm to solve this problem, improving upon the previously fastest $O(n^3)$ time algorithm, where $n$ is the number of vertices.

As an extension of a classical tree-partition problem, we consider decompositions of graphs into edge-disjoint (rooted-)trees with an additional matroid constraint. Specifically, suppose that we are given a graph $G=(V,E)$, a multiset ${\bm R} = \{r_1,\dots, r_t\}$ of vertices in $V$, and a matroid ${\cal M}$ on ${\bm R}$. We prove a necessary and sufficient condition for $G$ to be decomposed into $t$ edge-disjoint subgraphs $G_1=(V_1,T_1), \dots, G_t=(V_t,T_t)$ such that (i) for each $i$, $G_i$ is a tree with $r_i\in V_i$, and (ii) for each $v\in V$, the multiset $\{r_i\in {\bm R} \mid v\in V_i\}$ is a base of ${\cal M}$. If ${\cal M}$ is a free matroid, this is a decomposition into $t$ edge-disjoint spanning trees; thus, our result is a proper extension of Nash-Williams' tree-partition theorem. Such a matroid constraint is motivated by combinatorial rigidity theory. As a direct application of our decomposition theorem, we present characterizations of the infinitesimal rigidity of frameworks with nongeneric “boundary,” which extend classical the Laman's theorem for generic 2-rigidity of bar-joint frameworks and Tay's theorem for generic $d$-rigidity of body-bar frameworks.

A body-and-hinge framework is a structure consisting of rigid bodies connected by hinges in d-dimensional space. The generic infinitesimal rigidity of a body-and-hinge framework has been characterized in terms of the underlying graph independently by Tay and Whiteley as follows: A graph G can be realized as an infinitesimally rigid body-and-hinge framework by mapping each vertex to a body and each edge to a hinge if and only if ({d+1/2}-1)G contains {d+1/2} edge-disjoint spanning trees, where ({d+1/2}-1)G is the graph obtained from $G$ by replacing each edge by (d+1/2-1) parallel edges. In 1984 they jointly posed a question about whether their combinatorial characterization can be further applied to a nongeneric case. Specifically, they conjectured that G can be realized as an infinitesimally rigid body-and-hinge framework if and only if G can be realized as that with the additional "hinge-coplanar" property, i.e., all the hinges incident to each body are contained in a common hyperplane. This conjecture is called the Molecular Conjecture due to the equivalence between the infinitesimal rigidity of "hinge-coplanar" body-and-hinge frameworks and that of bar-and-joint frameworks derived from molecules in 3-dimension. In 2-dimensional case this conjecture has been proved by Jackson and Jordán in 2006. In this paper we prove this long standing conjecture affirmatively for general dimension. Also, as a corollary, we obtain a combinatorial characterization of the 3-dimensional bar-and-joint rigidity matroid of the square of a graph.

A non-crossing geometric graph is a graph embedded on a given set of points in the plane with non-crossing straight line segments. In this paper we present a new general framework for enumerating non-crossing geometric graphs for a given point set. By applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees and non-crossing minimally rigid frameworks. Furthermore, we also obtain efficient enumeration algorithms for non-crossing geometric graph classes, for which no enumeration algorithm has been reported so far, such as non-crossing matchings, non-crossing blue-and-red matchings, non-crossing k-vertex or k-edge connected graphs or non-crossing directed spanning trees. The proposed idea is relatively simple, and can be potentially applied to various other enumeration problems of non-crossing geometric graphs.

In this paper we will investigate the relationship between room layout and the rent of apartments by extracting meaningful substructures of a graph representing the room layout using a graph mining algorithm. We will then construct a prediction model for the rent of apartments with high accuracy. Through our analysis, we will reveal certain typical substructures in the room layout which strongly affect the rent.

We study the problem of rounding a real-valued matrix into an integer-valued matrix to minimize an L p -discrepancy measure between them. To define the L p -discrepancy measure, we introduce a family ${\cal F}$ of regions (rigid submatrices) of the matrix and consider a hypergraph defined by the family. The difficulty of the problem depends on the choice of the region family ${\cal F}$. We first investigate the rounding problem by using integer programming problems with convex piecewise-linear objective functions and give some nontrivial upper bounds for the L p discrepancy. We propose "laminar family" for constructing a practical and well-solvable class of ${\cal F}$. Indeed, we show that the problem is solvable in polynomial time if ${\cal F}$ is the union of two laminar families. Finally, we show that the matrix rounding using L 1 discrepancy for the union of two laminar families is suitable for developing a high-quality digital-halftoning software.

We give an algorithm to compute all the local peaks in the $k$-level o f an arrangement of $n$ lines in $O(n \log n) + \tilde{O}((kn)^{2/3})$ time. We can also find $\tau$ largest peaks in $O(n \log ^2 n) + \tilde{O}((\tau n)^{2/3})$ time. Moreover, we consider the longest edge in a parametric minimum spanning tree (in other words, a bottleneck edge for connectivity), and give an algorithm to compute the parameter value (within a given interval) maximizing/minimizing the length of the longest edge in MST. The time complexity is $\tilde{O}( n^{8/7}k^{1/7} + n k^{1/3})$.

We show that for any line l in space, there are at most k(k+1) tangent planes through l to the k-level of an arrangement of concave surfaces. This is a generalization of L. Lovasz's (1971) lemma, which is a key constituent in the analysis of the complexity of k-level of planes. Our proof is constructive, and finds a family of concave surfaces covering the "laminated at-most-k level". As consequences, (1): we have an O((n-k)/sup 2/3/n/sup 2/) upper bound for the complexity of the k-level of n triangle of space, and (2): we can extend the k-set result in space to the k-set of a system of subsets of n points.

We consider the problem of finding a set of k vertices in a graph that are in some sense remote. Stated more formally, given a graph G and an integer k, find a set P of k vertices for which the total weight of a minimum structure on P is maximized. In particular, we are interested in three problems of this type, where the structure to be minimized is a spanning tree ({\sc Remote-MST}), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for {\sc Remote-MST} is exactly 4, while this problem is NP-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.

Article Free Access Share on Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k Authors: Tetsuo Asano Dept. af Engr. Informatics, Osaka Electro-Communication University, Neyagawa 572, Japan Dept. af Engr. Informatics, Osaka Electro-Communication University, Neyagawa 572, JapanView Profile , Naoki Katoh Dept. of Management Science, Kobe university of Commerce, Kobe 651-21, Japan Dept. of Management Science, Kobe university of Commerce, Kobe 651-21, JapanView Profile , Hisao Tamaki IBM Tokyo Research Laboratory, Yamato 242, Japan IBM Tokyo Research Laboratory, Yamato 242, JapanView Profile , Takeshi Tokuyama IBM Tokyo Research Laboratory, Yamato 242, Japan IBM Tokyo Research Laboratory, Yamato 242, JapanView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 275–283https://doi.org/10.1145/258533.258602Online:04 May 1997Publication History 31citation606DownloadsMetricsTotal Citations31Total Downloads606Last 12 Months51Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

No abstract available.

In this paper we consider thek-clustering problem for a set S of n points i=(xi) in thed-dimensional space with variance-based errors as clustering criteria, motivated from the color quantization problem of computing a color lookup table for frame buffer display. As the inter-cluster criterion to minimize, the sum on intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster Sj,

Abstract LetG = (V, E)be an undirected graph withnvertices andmedges such that a real‐valued weight, denoted byw(e), is associated with each edgee. This paper studies what we call the minimum range cut problem that asks to find a cut inGsuch that the range of all edge weights in the cut is minimum. Here, the range of a cutCis defined to be the maximum difference among weights of edges in the cut, i.e., maxeϵcw(e)‐ mineϵcw(e). This paper proposes anO(m + nlogn) algorithm for the minimum range cut problem. It is also shown that this running time is optimal. We also study two variants of this problem. One is the minimum range target cut problem. Given a prespecified value called a target, this problem asks to find a cut with minimum range among all cuts such that the target value is between the minimum and maximum of weights of edges in the cut. The second is the minimum ranges – tcut problem that asks to find ans – tcut with minimum range. This paper proposesO(m + nlogn) algorithms for these problems. For the second problem, we show that anancestor treeofO(n)space recently developed by Cheng and Hu effectively represents all pairs minimum range cuts, which can be constructed inO(n2)time, and enables us to answer any minimum ranges – tcut query inO(1)time [resp., inO(n)time] if we want to obtain only the range value of the cut (resp., the bipartition of vertices induced by the cut). © 1994 by John Wiley & Sons, Inc.

Abstract A graph‐theoretical model is presented for scheduling the transmission of messages in a computer network. A related wiring problem is also discussed; connections with classical edge colorings are exhibited and optimality properties are discussed. © 1993 by John Wiley & Sons, Inc.

We study the problem of enumerating k farthest pairs for n points in the plane and the problems of enumerating k closest/farthest bichromatic pairs of n red and n blue points in the plane. We propose a new technique for geometric enumeration problems which iteratively reduces the search space by a half and provides efficient algorithms. As applications of this technique, we develop algorithms, using higher order Voronoi diagrams, for the above problems, which run in O(min{n2, n log n + k4/3 log n/log1/3k}) time and O(n+k4/3/(log k)1/3+k log n) space. Since, to the authors' knowledge, no nontrivial algorithms have been known for these problems, our algorithms are currently fastest when k=o(n3/2).

The authors investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Suppose that one is given a set of n points in general d-dimensional space, S=(p/sub 1/,p/sub 2/, . . ., p/sub n/), and that all points move along different straight lines at different but fixed speeds, i.e., the position of p/sub i/ is a linear function of a real parameter. They investigate the numbers of transitions of MinST and MaxST when t increases from - infinity to + infinity . They assume that the dimension d is a fixed constant. Since there are O(n/sup 2/) distances among n points, there are naively O(n/sup 4/) transitions of MinST and MaxST. They improve these trivial upper bounds for L/sub 1/ and L/sub infinity / distance metrics. Let c/sub p/(n, min) (resp. c/sub p/(n, max)) be the number of maximum possible transitions of MinST (resp. MaxST) in L/sub p/ metric for n linearly moving points. They give the following results; c/sub 1/(n, min)=O(n/sup 5/2/a(n)), c/sub infinity /(n, min)=O(n/sup 5/2/a(n)), c/sub 1/(n, max)=O(n/sup n/) and c/sub infinity /(n, max)=O(n/sup 2/) where O(n) is the inverse Ackermann function. They also investigate two restricted cases.>

Abstract This paper considers a sharing problem of distributing a given quantity of resources to a set of demand nodes in a network as equally as possible. We study the case in which the resources are of two distinct kinds and propose a polynomial time algorithm for it by reducing the problem to the one‐commodity sharing problem.

Let MC stand for a class of logs (i.e. sequences of read/write steps of transactions) that are serializable when multiple versions of the data items are maintained. The multiversion cautious scheduler, MCS(MC) which is introduced, outputs a sequence belonging to MC by reordering, if necessary, the incoming sequence of requests from transactions and it never resorts to rollbacks. In the model, transactions on arrival predeclare their read sets and write sets. It is shown that MCS(MWW) and MCS(MWRW) can be executed in polynomial time, where MWW and MWRW are multiversion classes of logs serializable under the write-write and write-read-write constraints respectively. For any multiversion class MC of interest, MCS(MC) does not exhibit cancellation anomaly, i.e. it functions correctly even if some of the predeclared steps are canceled. Furthermore, MCS(MWW) functions correctly, even if transactions issue more read operations than they predeclared. Thus, MCS(MWW) allows each transaction to predeclare only its write set.>

Article Free Access Share on Fining k points with minimum spanning trees and related problems Authors: A. Aggarwal IBM T. J. Watson Research Center IBM T. J. Watson Research CenterView Profile , H. Imai Kyushu University, Japan Kyushu University, JapanView Profile , N. Katoh Kobe University of Commerce, Japan Kobe University of Commerce, JapanView Profile , S. Suri Bell Communications Research Bell Communications ResearchView Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989 Pages 283–291https://doi.org/10.1145/73833.73865Published:05 June 1989Publication History 7citation660DownloadsMetricsTotal Citations7Total Downloads660Last 12 Months14Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Cautious schedulers, which never resort to rollbacks for the purpose of concurrency control, are investigated. In particular, cautious schedulers for classes WW consisting of schedules serializable under the write-write constraints, and WRW, a superclass of W, are considered. The cautious WW-scheduler has a number of nice properties, one of which is the existence of a polynomial-time scheduling algorithm. Since cautious WRW-scheduling is, in general, NP-complete, some restrictions are introduced which allow polynomial-time scheduling. All of these cautious schedulers are based on the assumption that transaction predeclare their read and write sets on arrival. Anomalies which occur when transaction modify their read sets or write sets during execution are discussed and countermeasures are proposed.>

We propose a new class of schedulers, called cautious schedulers , that grant an input request if it will not necessitate any rollback in the future. In particular, we investigate cautious WRW-schedulers that output schedules in class WRW only. Class WRW consists of all schedules that are serializable, while preserving the write-read and read-write conflict, and is the largest polynomially recognizable subclass of serializable schedules currently known. It is shown, in this paper however, that cautious WRW- scheduling is, in general, NP-complete. Therefore, we introduce a special type ( type 1R ) of transaction, which consists of no more than one read step (an indivisible set of read operations) followed by multiple write steps. It is shown that cautious WRW-scheduling can be performed efficiently if all transactions are of type 1R and if admission control can be exercised. Admission control rejects a transaction unless its first request is immediately grantable.

Abstract This article gives an efficient algorithm for obtaining K shortest simple paths between two specified nodes in an undirected graph G with non‐negative edge lengths. Letting n be the number of nodes and m be the number of edges in G, its running time is O(Kc(n, m)) if the shortest paths from one node to all the other nodes are obtained in c(n, m) [≥O(m)] time, and the required space is O(Kn + m). This time bound is better than those realized by existing algorithms, the best of which, proposed by Yen, requires O(Kn3) time, since c(n, m) ≤min[O(n2), O(m log n)] is known.

An algorithm is presented for obtaining the K best solutions of the resource allocauon problem with an objective function which is the sum of convex functions of one variable It requires O(T* + Klog K + Kn~ogn) time and O(Kn~ogn + n) space, where n is the number of variables and T* ~s the computatmnal time to obtain the best solution KEY WORDS AND PHRASES resource aUocatmn problem, K best soluuons, computational complexity CR CATEGORIES 5 25, 5 30, 5 41 O(Nlogn + n).The method of [27] requires O(c(n, N) + nlogn) time, where c(n, N) is the time required to solve the continuous problem P' obtained from P by dropping the integrality condition on the x,.A third type of approach is exemplified by [6, 7,

This paper presents an algorithm for finding K minimum spanning trees in an undirected graph. The required time is $O(Km + \min (n^2 ,m\log \log n))$ and the space is $O(K + m)$, where n is the number of vertices and m is the number of edges. The algorithm is based on three subroutines. The first two subroutines are used to obtain the second minimum spanning tree in $O(\min (n^2 ,m\alpha (m,n)))$ steps, where $\alpha (m,n)$ is Tarjan’s inverse of Ackermann’s function [12] which is very slowly growing. The third one obtains the kth minimum spanning tree in $O(m)$ steps when the jth minimum spanning trees for $j = 1,2, \cdots ,k - 1$ are given.