A constant factor approximation algorithm for boxicity of circular arc graphs

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

Monopoles, Dirac operator, and index theory for fuzzy SU(3) / (U(1) x U(1))

The intersection of the ten-dimensional fuzzy conifold Y-F(10) with S-F(5) x S-F(5) is the compact eight-dimensional fuzzy space X-F(8). We show that X-F(8) is (the analogue of) a principal U(1) x U(1) bundle over fuzzy SU(3) / U(1) x U(1)) ( M-F(6)). We construct M-F(6) using the Gell-Mann matrices by adapting Schwinger's construction. The space M-F(6) is of relevance in higher dimensional quantum Hall effect and matrix models of D-branes. Further we show that the sections of the monopole bundle can be expressed in the basis of SU(3) eigenvectors. We construct the Dirac operator on M-F(6) from the Ginsparg-Wilson algebra on this space. Finally, we show that the index of the Dirac operator correctly reproduces the known results in the continuum.

LOWER BOUNDS FOR BOXICITY

An axis-parallel b-dimensional box is a Cartesian product R-1 x R-2 x ... x R-b where R-i is a closed interval of the form a(i),b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension b, such that G is representable as the intersection graph of boxes in b-dimensional space. Although boxicity was introduced in 1969 and studied extensively, there are no significant results on lower bounds for boxicity. In this paper, we develop two general methods for deriving lower bounds. Applying these methods we give several results, some of which are listed below: 1. The boxicity of a graph on n vertices with no universal vertices and minimum degree delta is at least n/2(n-delta-1). 2. Consider the g(n,p) model of random graphs. Let p <= 1 - 40logn/n(2.) Then with high `` probability, box(G) = Omega(np(1 - p)). On setting p = 1/2 we immediately infer that almost all graphs have boxicity Omega(n). Another consequence of this result is as follows: For any positive constant c < 1, almost all graphs on n vertices and m <= c((n)(2)) edges have boxicity Omega(m/n). 3. Let G be a connected k-regular graph on n vertices. Let lambda be the second largest eigenvalue in absolute value of the adjacency matrix of G. Then, the boxicity of G is a least (kappa(2)/lambda(2)/log(1+kappa(2)/lambda(2))) (n-kappa-1/2n). 4. For any positive constant c 1, almost all balanced bipartite graphs on 2n vertices and m <= cn(2) edges have boxicity Omega(m/n).

On strong centerpoints

Let P be a set of n points in R-d and F be a family of geometric objects. We call a point x is an element of P a strong centerpoint of P w.r.t..F if x is contained in all F is an element of F that contains more than cn points of P, where c is a fixed constant. A strong centerpoint does not exist even when F is the family of halfspaces in the plane. We prove the existence of strong centerpoints with exact constants for convex polytopes defined by a fixed set of orientations. We also prove the existence of strong centerpoints for abstract set systems with bounded intersection. (C) 2014 Elsevier B.V. All rights reserved.

Boxicity and cubicity of product graphs

The boxicity (cubicity) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in R-k. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d, of the boxicity and the cubicity of the dth power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the dth Cartesian power of any given finite graph is, respectively, in O(log d/ log log d) and circle dot(d/ log d). On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products. (C) 2015 Elsevier Ltd. All rights reserved.

Interdiffusion and solid solution strengthening in Ni-Co-Pt and Ni-Co-Fe ternary systems

Diffusion couple experiments are conducted in Co-Ni-Pt system at 1200 degrees C and in Co-Ni-Fe system at 1150 degrees C, by coupling binary alloys with the third element. Uphill diffusion is observed for both Co and Ni in Pt rich corner of the Co-Ni-Pt system, whereas in the Co-Ni-Fe system, it is observed for Co. Main and cross interdiffusion coefficients are calculated at the composition of intersection of two independent diffusion profiles. In both the systems, the main interdiffusion coefficients are positive over the whole composition range and the cross interdiffusion coefficients show both positive and negative values at different regions. Hardness measured by performing the nanoindentations on diffusion couples of both the systems shows the higher values at intermediate compositions.

Kinematics and dynamics of Jansen leg mechanism: A bond graph approach

The Jansen mechanism is a one degree-of-freedom, planar, 12-link, leg mechanism that can be used in mobile robotic applications and in gait analysis. This paper presents the kinematics and dynamics of the Jansen leg mechanism. The forward kinematics, accomplished using circle intersection method, determines the trajectories of various points on the mechanism in the chassis (stationary link) reference frame. From the foot point trajectory, the step length is shown to vary linearly while step height varies non-linearly with change in crank radius. A dynamic model for the Jansen leg mechanism is proposed using bond graph approach with modulated multiport transformers. For given ground reaction force pattern and crank angular speed, this model helps determine the motor torque profile as well as the link and joint stresses. The model can therefore be used to rate the actuator torque and in design of the hardware and controller for such a system. The kinematics of the mechanism can also be obtained from this dynamic model. The proposed model is thus a useful tool for analysis and design of systems based on the Jansen leg mechanism. (C) 2015 Elsevier B.V. All rights reserved.

Efficient Protocol for Authenticated Email Search

Executing authenticated computation on outsourced data is currently an area of major interest in cryptology. Large databases are being outsourced to untrusted servers without appreciable verification mechanisms. As adversarial server could produce erroneous output, clients should not trust the server's response blindly. Primitive set operations like union, set difference, intersection etc. can be invoked on outsourced data in different concrete settings and should be verifiable by the client. One such interesting adaptation is to authenticate email search result where the untrusted mail server has to provide a proof along with the search result. Recently Ohrimenko et al. proposed a scheme for authenticating email search. We suggest significant improvements over their proposal in terms of client computation and communication resources by properly recasting it in two-party settings. In contrast to Ohrimenko et al. we are able to make the number of bilinear pairing evaluation, the costliest operation in verification procedure, independent of the result set cardinality for union operation. We also provide an analytical comparison of our scheme with their proposal which is further corroborated through experiments.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.

Shock-Induced Near-Wall Two-Phase Flow Structure Over a Micron-Sized Particles Bed

The present paper studies numerical modelling of near-wall two-phase flows induced by a normal shock wave moving at a constant speed, over a micronsized particles bed. In this two-fluid model, the possibility of particle trajectory intersection is considered and a full Lagrangian formulation of the dispersed phase is introduced. The finiteness of the Reynolds and Mach numbers of the flow around a particle as well as the fineness of the particle sizes are taken into account in describing the interactions between the carrier- and dispersed- phases. For the small mass-loading ratio case, the numerical simulation of flow structure of the two phases is implemented and the profiles of the particle number density are obtained under the constant-flux condition on the wall. The effects of the shock Mach number and the particle size and material density on particle entrainment motion are discussed in detail.The obtained results indicate that interphase non-equilibrium in the velocity and temperature is a common feature for this type of flows and a local particle accumulation zone may form near the envelope of the particle trajectory family.

Teología pastoral Inter Loci : una disciplina teológica ante el aporte de las experiencias creyentes en escenarios sociales contemporáneos

Resumen: El texto realiza una relectura del método Ver-Juzgar-Actuar teniendo en cuenta el acercamiento biográfico que ofrecen las ciencias sociales. Propone considerar que la Teología Pastoral desarrolla así un discurso sobre la Iglesia, la Academia y la Plaza Pública en el cruce que estos ámbitos tienen en las mismas prácticas cristianas, dando lugar a una Teología Inter Loci. Y describe el perfil teológico emergente en dicha experiencia utilizando el marco de las inteligencias múltiples.

Annual report 2005 - North Pacific Marine Science Organization (PICES). Fourteenth meeting, Vladivostok, Russia, September 29-October 9, 2005

Report of Opening Session (pdf 0.07 Mb) Report of Governing Council (pdf 0.2 Mb) Report of the Finance and Administration Committee (pdf 0.07 Mb) Reports of Science Board and Committees Science Board inter-sessional meeting (pdf 0.07 Mb) Science Board (pdf 0.1 Mb) Biological Oceanography Committee (pdf 0.2 Mb) Fishery Science Committee (pdf 0.04 Mb) Marine Environmental Quality Committee (pdf 0.06 Mb) MONITOR Technical Committee (pdf 0.05 Mb) Physical Oceanography and Climate Committee (pdf 0.06 Mb) Technical Committee on Data Exchange (pdf 0.04 Mb) Reports of Sections, Working and Study Groups Section on Ecology of harmful algal blooms in the North Pacific (pdf 0.03 Mb) Section on Carbon and Climate Working Group 18 on Mariculture in the 21st century - The intersection between ecology, socio-economics and production (pdf 0.06 Mb) Working Group 19 on Ecosystem-based management science and its application to the North Pacific (pdf 0.03 Mb) Reports of the Climate Change and Carrying Capacity Program Implementation Panel on the CCCC Program (pdf 0.04 Mb) CFAME Task Team (pdf 0.04 Mb) MODEL Task Team (pdf 0.04 Mb) Reports of Advisory Panels Advisory Panel on Iron Fertilization Experiment in the Subarctic Pacific Ocean (pdf 0.04 Mb) Advisory Panel on Marine Birds and Mammals (pdf 0.03 Mb) Advisory Panel on Micronekton Sampling Inter-Calibration experiment (pdf 0.05 Mb) Summary of Scientific Sessions and Workshops (pdf 0.2 Mb) Membership List (pdf 0.07 Mb) List of Participants (pdf 0.07 Mb) List of Acronyms (pdf 0.03 Mb)

Annual report 2004 - North Pacific Marine Science Organization (PICES). Thirteenth meeting, Honolulu, Hawaii, U.S.A., October 14-24, 2004

Report of Opening Session (pdf 0.07 Mb) Report of Governing Council (pdf 0.2 Mb) Report of the Finance and Administration Committee (pdf 0.08 Mb) Reports of Science Board and Committees Science Board inter-sessional meeting (pdf 0.05 Mb) Science Board (pdf 0.1 Mb) Biological Oceanography Committee (pdf 0.1 Mb) Fishery Science Committee (pdf 0.04 Mb) Marine Environmental Quality Committee (pdf 0.04 Mb) Physical Oceanography and Climate Committee (pdf 0.04 Mb) Technical Committee on Data Exchange (pdf 0.04 Mb) Reports of Sections, Working and Study Groups Harmful Algal Blooms Section (pdf 0.03 Mb) Working Group 17 on Biogeochemical data integration and synthesis (pdf 0.03 Mb) Working Group 18 on Mariculture in the 21st century - The intersection between ecology, socio-economics and production (pdf 0.06 Mb) Study Group on Ecosystem-based management science and its application to the North Pacific (pdf 0.04 Mb) Reports of the Climate Change and Carrying Capacity Program Implementation Panel on the CCCC Program (pdf 0.04 Mb) BASS Task Team (pdf 0.04 Mb) CFAME Task Team (pdf 0.04 Mb) MODEL Task Team (pdf 0.04 Mb) MONITOR Task Team (pdf 0.03 Mb) REX Task Team (pdf 0.04 Mb) Reports of Advisory Panels Advisory Panel on Continuous Plankton Recorder Survey in the North Pacific (pdf 0.4 Mb) Advisory Panel on Iron Fertilization Experiment in the Subarctic Pacific Ocean (pdf 0.03 Mb) Advisory Panel on Marine Birds and Mammals (pdf 0.04 Mb) Advisory Panel on Micronekton Sampling Inter-Calibration experiment (pdf 0.04 Mb) Summary of Scientific Sessions and Workshops (pdf 0.2 Mb) Membership List (pdf 0.07 Mb) List of Participants (pdf 0.09 Mb) List of Acronyms (pdf 0.03 Mb)

Integration property of a wedge-elliptic cone waverider with scramjet engine

The hypersonic waverider forebody is designed in this paper. For the present waverider, the undersurface is carved out as a stream surface of a hypersonic inviscid flow field around wedge-elliptic cone, and the upper surface is assumed to be a freestream surface. A finite-volume code is used to generate the three-dimensional flow field. The leading edge is determined by satisfying the condition that the lip is situated at the intersection line of shocks.

Some Results on Fixed and Best Proximity Points of Multivalued

This paper is devoted to investigate the fixed points and best proximity points of multivalued cyclic self-mappings on a set of subsets of complete metric spaces endowed with a partial order under a generalized contractive condition involving a Hausdorff distance. The existence and uniqueness of fixed points of both the cyclic self-mapping and its associate composite self-mappings on each of the subsets are investigated, if the subsets in the cyclic disposal are nonempty, bounded and of nonempty convex intersection. The obtained results are extended to the existence of unique best proximity points in uniformly convex Banach spaces.