In the era of Big Data, Cloud Computing and Internet of Things, most of the existing, integrated solutions that attempt to solve their challenges are either proprietary, limit functionality to a ...predefined set of requirements, or hide the way data are stored and accessed. In this work we propose Cenote, an open source Big Data management and analytics infrastructure for the Web of Things that overcomes the above limitations. Cenote is built on component-based software engineering principles and provides an all-inclusive solution based on components that work well individually.
In the era of Big Data, Cloud Computing and Internet of Things, most of the existing, integrated solutions that attempt to solve their challenges are either proprietary, limit functionality to a ...predefined set of requirements, or hide the way data are stored and accessed. In this work we propose Cenote, an open source Big Data management and analytics infrastructure for the Web of Things that overcomes the above limitations. Cenote is built on component-based software engineering principles and provides an all-inclusive solution based on components that work well individually.
Given two graphs $G$ and $H$, we define $\textsf{v-cover}_{H}(G)$ (resp.
$\textsf{e-cover}_{H}(G)$) as the minimum number of vertices (resp. edges)
whose removal from $G$ produces a graph without any ...minor isomorphic to ${H}$.
Also $\textsf{v-pack}_{H}(G)$ (resp. $\textsf{v-pack}_{H}(G)$) is the maximum
number of vertex- (resp. edge-) disjoint subgraphs of $G$ that contain a minor
isomaorphic to $H$. We denote by $\theta_r$ the graph with two vertices and $r$
parallel edges between them. When $H=\theta_r$, the parameters
$\textsf{v-cover}_{H}$, $\textsf{e-cover}_{H}$, $\textsf{v-pack}_{H}$, and
$\textsf{v-pack}_{H}$ are NP-hard to compute (for sufficiently big values of
$r$). Drawing upon combinatorial results in Minors in graphs of large
$\theta_r$-girth, Chatzidimitriou et al., arXiv:1510.03041, we give an
algorithmic proof that if $\textsf{v-pack}_{\theta_r}(G)\leq k$, then
$\textsf{v-cover}_{\theta_r}(G) = O(k\log k)$, and similarly for
$\textsf{v-pack}_{\theta_r}$ and $\textsf{e-cover}_{\theta_r}$. In other words,
the class of graphs containing ${\theta_r}$ as a minor has the vertex/edge
Erd\H{o}s-P\'osa property, for every positive integer $r$. Using the
algorithmic machinery of our proofs, we introduce a unified approach for the
design of an $O(\log {\rm OPT})$-approximation algorithm for
$\textsf{v-pack}_{\theta_r}$, $\textsf{v-cover}_{\theta_r}$,
$\textsf{v-pack}_{\theta_r}$, and $\textsf{e-cover}_{\theta_r}$ that runs in
$O(n\cdot \log(n)\cdot m)$ steps. Also, we derive several new
Erd\H{o}s-P\'osa-type results from the techniques that we introduce.
For every $r \in \mathbb{N}$, let $\theta_r$ denote the graph with two
vertices and $r$ parallel edges. The $\theta_r$-girth of a graph $G$ is the
minimum number of edges of a subgraph of $G$ that ...can be contracted to
$\theta_r$. This notion generalizes the usual concept of girth which
corresponds to the case $r=2$. In Minors in graphs of large girth, Random
Structures & Algorithms, 22(2):213--225, 2003, K\"uhn and Osthus showed that
graphs of sufficiently large minimum degree contain clique-minors whose order
is an exponential function of their girth. We extend this result for the case
of $\theta_{r}$-girth and we show that the minimum degree can be replaced by
some connectivity measurement. As an application of our results, we prove that,
for every fixed $r$, graphs excluding as a minor the disjoint union of $k$
$\theta_{r}$'s have treewidth $O(k\cdot \log k)$.
Given two graphs \(G\) and \(H\), we define \(\textsf{v-cover}_{H}(G)\) (resp. \(\textsf{e-cover}_{H}(G)\)) as the minimum number of vertices (resp. edges) whose removal from \(G\) produces a graph ...without any minor isomorphic to \({H}\). Also \(\textsf{v-pack}_{H}(G)\) (resp. \(\textsf{v-pack}_{H}(G)\)) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of \(G\) that contain a minor isomaorphic to \(H\). We denote by \(\theta_r\) the graph with two vertices and \(r\) parallel edges between them. When \(H=\theta_r\), the parameters \(\textsf{v-cover}_{H}\), \(\textsf{e-cover}_{H}\), \(\textsf{v-pack}_{H}\), and \(\textsf{v-pack}_{H}\) are NP-hard to compute (for sufficiently big values of \(r\)). Drawing upon combinatorial results in Minors in graphs of large \(\theta_r\)-girth, Chatzidimitriou et al., arXiv:1510.03041, we give an algorithmic proof that if \(\textsf{v-pack}_{\theta_r}(G)\leq k\), then \(\textsf{v-cover}_{\theta_r}(G) = O(k\log k)\), and similarly for \(\textsf{v-pack}_{\theta_r}\) and \(\textsf{e-cover}_{\theta_r}\). In other words, the class of graphs containing \({\theta_r}\) as a minor has the vertex/edge Erdős-Pósa property, for every positive integer \(r\). Using the algorithmic machinery of our proofs, we introduce a unified approach for the design of an \(O(\log {\rm OPT})\)-approximation algorithm for \(\textsf{v-pack}_{\theta_r}\), \(\textsf{v-cover}_{\theta_r}\), \(\textsf{v-pack}_{\theta_r}\), and \(\textsf{e-cover}_{\theta_r}\) that runs in \(O(n\cdot \log(n)\cdot m)\) steps. Also, we derive several new Erdős-Pósa-type results from the techniques that we introduce.
For every \(r \in \mathbb{N}\), let \(\theta_r\) denote the graph with two vertices and \(r\) parallel edges. The \(\theta_r\)-girth of a graph \(G\) is the minimum number of edges of a subgraph of ...\(G\) that can be contracted to \(\theta_r\). This notion generalizes the usual concept of girth which corresponds to the case \(r=2\). In Minors in graphs of large girth, Random Structures & Algorithms, 22(2):213--225, 2003, K\"uhn and Osthus showed that graphs of sufficiently large minimum degree contain clique-minors whose order is an exponential function of their girth. We extend this result for the case of \(\theta_{r}\)-girth and we show that the minimum degree can be replaced by some connectivity measurement. As an application of our results, we prove that, for every fixed \(r\), graphs excluding as a minor the disjoint union of \(k\) \(\theta_{r}\)'s have treewidth \(O(k\cdot \log k)\).
