105,329 research outputs found
On the approximability of the L(h, k)-labelling problem on bipartite graphs (Extended abstract)
No full textGiven an undirected graph G, an L(h, k)-labelling of G assigns colors to vertices from the integer set {0,.. lambda(h,k)}, such that any two vertices v(i) and v(j) receive colors c(v(i)) and c(v(j)) satisfying the following conditions: i) if v(i) and v(j) are adjacent then vertical bar c(v(i)) - c(v(j))vertical bar >= h; ii) if v(i) and v(j) are at distance two then vertical bar c(v(i)) - c(v(j))vertical bar >= k. The aim of the L(h, k)-labelling problem is to minimize lambda(h,k)- In this paper we study the approximability of the L(h,k)-labelling problem on bipartite graphs and extend the results to s-partite and general graphs. Indeed, the decision version of this problem is known to be DIP-complete in general and, to our knowledge, there are no polynomial solutions, either exact or approximate, for bipartite graphs. Here, we state some results concerning the approximability of the L(h,k)-labelling problem for bipartite graphs, exploiting a novel technique, consisting in computing approximate vertex- and edge-colorings of auxiliary graphs to deduce an L(h, k)-labelling for the input bipartite graph. We derive an approximation algorithm with performance ratio bounded by (4)/D-3(2), where, D is equal to the minimum even value bounding the minimum of the maximum degrees of the two partitions. One of the above coloring algorithms is in fact an approximating edge-coloring algorithm for hypergraphs of maximum dimension d, i.e. the maximum edge cardinality, with performance ratio d. Furthermore, we consider a different approximation technique based on the reduction of the L(h, k)-labelling problem to the vertex-coloring of the square of a graph. Using this approach we derive an approximation algorithm with performance ratio bounded by min(h, 2k)root n + o(k root n), assuming h >= k. Hence, the first technique is competitive when D O(n(1/4)) These algorithms match with a result in [2] stating that L(1,1) labelling n-vertex bipartite graphs is hard to approximate within(n1/2-)epsilon, for any epsilon > 0, unless NP=ZPP. We then extend the latter approximation strategy to s-partite graphs, obtaining a (min(h, sk)root n + o(sk root n))-approximation ratio, and to general graphs deriving an (h root n + o(h root n))-approximation algorithm, assuming h >= k. Finally, we prove that the L(h, k)-labelling problem is not easier than coloring the square of a graph
Solar Physics with LISA
No full textGalactic cosmic rays and solar energetic particles (SEPs) with energies larger than 100 MeV/n are able to penetrate and charge the test masses of the LISA experiment. As this process constitutes one of the major sources of noise for the experiment, a small telescope of silicon detectors will be located on board the LISA PathFinder and, possibly, the three LISA spacecraft. This device will allow us to monitor real-time galactic and solar cosmic-ray incident proton fluxes above 100 MeV. Moreover, spectral information will be provided up to an energy of 500 MeV. We propose to use the above instrument for the evaluation of the test mass charging process and the study of SEPs accelerated by coronal mass ejection (CME) propagation. Because of the peculiar orbit of the LISA spacecraft around the Sun, this experiment offers a unique chance to monitor an evolving CME contemporary at 2 degrees (among spacecraft) and 20 degrees (between LISA and Earth) intervals in longitude at once. These observations are of particular interest for both solar physics and space weather investigations. SEP event occurrence is not predictable and these events are particularly dangerous to astronauts and space equipment
L(h,1,1)-Labeling of Outerplanar Graphs
No full textAn -labeling of a graph is an assignment of labels from the set of integers
to the vertices of the graph such that adjacent
vertices are assigned integers of at least distance apart
and all vertices of distance three or less must be assigned different labels.
%%(except for , where adjacent nodes may have the same label).
The aim of the -labeling problem is to minimize ,
denoted by and called \emph{span} of the -labeling.
As outerplanar graphs have bounded treewidth, the -labeling problem on outerplanar graphs can be exactly solved in , but the multiplicative factor depends on the maximum degree and is too big to be of practical use. %where the multiplicative constant is exponential in their maximum degree .
In this paper we give a linear time approximation algorithm for computing the more general -labeling for outerplanar graphs that is within additive constants of the optimum values
Proximity Drawings: Three Dimensions Are Better than Two (Extended Abstract)
No full textWe consider weak Gabriel drawings of unbounded degree trees in the three-dimensional space. We assume a minimum distance between any two vertices. Under the same assumption, there exists an exponential area lower bound for general graphs. Moreover, all previously known algorithms to construct (weak) proximity drawings of trees, generally produce exponential area layouts, even when we restrict ourselves to binary trees. In this paper we describe a linear-time polynomial-volume algorithm that constructs a strictly-upward weak Gabriel drawing of any rooted tree with O(logn)-bit requirement. As a special case we describe a Gabriel drawing algorithm for binary trees which produces integer coordinates and n^3-area representations . Finally, we show that an infinite class of graphs requiring exponential area, admits linear-volume Gabriel drawings.The latter result can also be extended to \beta -drawings, for any 1< \beta <2, and relative neighborhood drawings
L(h,1,1)-Labeling of Outerplanar Graphs
No full textAn L(h, 1, 1)-labeling of a graph is an assignment of labels from the set of integers {0, . . . , λ} to the nodes of the graph such that adjacent nodes are assigned integers of at least distance h ≥ 1 apart and all nodes of distance three or less must be assigned different labels. The aim of the L(h, 1, 1)-labeling problem is to minimize λ, denoted by λ h, 1, 1 and called span of the L(h, 1, 1)-labeling. As outerplanar graphs have bounded treewidth, the L(1, 1, 1)-labeling problem on outerplanar graphs can be exactly solved in O(n 3), but the multiplicative factor depends on the maximum degree Δ and is too big to be of practical use. In this paper we give a linear time approximation algorithm for computing the more general L(h, 1, 1)-labeling for outerplanar graphs that is within additive constants of the optimum values
L(h, 1, 1)-labeling of outerplanar graphs
No full textAn L(h, 1, 1)-labeling of a graph is an assignment of labels from the set of integers {0, . . . , lambda} to the nodes of the graph such that adjacent nodes are assigned integers of at least distance h a parts per thousand yen 1 apart and all nodes of distance three or less must be assigned different labels. The aim of the L(h, 1, 1)-labeling problem is to minimize lambda, denoted by lambda (h, 1, 1) and called span of the L(h, 1, 1)-labeling. As outerplanar graphs have bounded treewidth, the L(1, 1, 1)-labeling problem on outerplanar graphs can be exactly solved in O(n (3)), but the multiplicative factor depends on the maximum degree Delta and is too big to be of practical use. In this paper we give a linear time approximation algorithm for computing the more general L(h, 1, 1)-labeling for outerplanar graphs that is within additive constants of the optimum values
L(h, 1, 1)-Labeling of Outerplanar Graphs
No full textAn L(h,1,1)-labeling of a graph is an assignment of labels from the set of integers {0, ⋯, λ} to the vertices of the graph such that adjacent vertices are assigned integers of at least distance h ≥1 apart and all vertices of distance three or less must be assigned different labels. The aim of the L(h,1,1)-labeling problem is to minimize λ, denoted by λ h,1,1 and called span of the L(h,1,1)-labeling.
As outerplanar graphs have bounded treewidth, the L(1,1,1)-labeling problem on outerplanar graphs can be exactly solved in O(n 3), but the multiplicative factor depends on the maximum degree Δ and is too big to be of practical use. In this paper we give a linear time approximation algorithm for computing the more general L(h,1,1)-labeling for outerplanar graphs that is within additive constants of the optimum values
Efficient data structure for lattice operations
No full textIn this paper, we consider the representation and management of an element set on which a lattice partial order relation is defined. In particular, let n be the element set size. We present an O(n root n)-space implicit data structure for performing the following set of basic operations: 1. Test the presence of an order relation between two given elements, in constant time. 2. Find a path between two elements whenever one exists, in O(l) steps, where l is the path length. 3. Compute the successors and/or predecessors set of a given element, in O(h) steps, where h is the size of the returned set. 4. Given two elements, find all elements between them, in time O(k log d), where k is the size of the returned set and d is the maximum in-degree or out-degree in the transitive reduction of the order relation. 5. Given two elements, find the least common ancestor and/or the greatest common successor in O(root n)-time. 6. Given k elements, find the least common ancestor and/or the greatest common successor in O(root n + k log n)time. (Unless stated otherwise, all logarithms are to the base 2.) The preprocessing time is O(n(2)). Focusing on the first operation, representing the building-box for all the others, we derive an overall O(n root n)-space x time bound which beats the order n(2) bottleneck representing the present complexity for this problem. Moreover, we will show that the complexity bounds for the first three operations are optimal with respect to the worst case. Additionally, a stronger result can be derived. In particular, it is possible to represent a lattice in space O(n root t), where t is the minimum number of disjoint chains which partition the element set
An Efficient Data Structure for Lattice Operations
No full textIn this paper, we consider the representation and management
of an element set on which a lattice partial order relation
is defined.
In particular, let
be the element set size, we present
an \nradn-space {\em implicit} data
structure for performing the
following set of basic operations:
\begin {itemize}
\item[1.] test the presence of an order relation between two given elements, in constant time;
\item[2.] find a path between two elements whenever one exists, in
steps, where
is the path length;
\item[3.] compute the successors and/or predecessors set of a given element,
in steps, where
is the size of the returned set;
\item[4.] given two elements, find all elements between them,
in time , where is the size of the returned set and
is the maximum indegree or outdegree in the transitive reduction of the
order relation;
\item[5.] given two elements, find the least common ancestor and/or the greatest common
successor in -time;
\item[6.] given elements, find the least common ancestor and/or the greatest common
successor in
\footnote{Unless stated otherwise, all logarithms are to the base 2.}-time.
\end {itemize}
The pre-processing time is
.
Focusing on the first operation, representing the building-box for all the others, we derive an overall
\nradn-spacetime bound which beats the order bottle-neck representing the present
complexity for this problem. Moreover, we will show that the complexity
bounds for the first three operations are optimal with
respect to the worst case. Additionally, a stronger result can be
derived. In particular, it is possible to represent a lattice in space
, where is the minimum number of disjoint chains which
partition the element set
L(h,1,1)-labeling of outerplanar graphs
No full textAn L(h, 1, 1)-labeling of a graph is an assignment of labels from the set of integers {0, ⋯, λ} to the vertices of the graph such that adjacent vertices are assigned integers of at least distance h ≥ 1 apart and all vertices of distance three or less must be assigned different labels. The aim of the L(h, 1, 1)-labeling problem is to minimize λ, denoted by λh,1,1 and called span of the L(h, 1, 1)-labeling. As outerplanar graphs have bounded treewidth, the L(1, 1, 1)-labeling problem on outerplanar graphs can be exactly solved in O(n3), but the multiplicative factor depends on the maximum degree Δ and is too big to be of practical use. In this paper we give a linear time approximation algorithm for computing the more general L(h, 1, 1)-labeling for outer-planar graphs that is within additive constants of the optimum values. © Springer-Verlag Berlin Heidelberg 2006
- …
