9 Search Results for "B�se, Joos-Hendrik"


Document
The Complexity of Computing Optimum Labelings for Temporal Connectivity

Authors: Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph G, what is the smallest number |λ| of time-labels that we need to add to the edges of G such that the resulting temporal graph (G,λ) is temporally connected? As it turns out, this basic problem, called Minimum Labeling (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem Min. Aged Labeling (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e., maximum label) of the obtained temporal graph (G,λ). Second we consider the problem Min. Steiner Labeling (MSL), where the aim is now to have a temporal path between any pair of "important" vertices which lie in a subset R ⊆ V, which we call the terminals. This relaxed problem resembles the problem Steiner Tree in static (i.e., non-temporal) graphs. However, due to the requirement of strictly increasing labels in a temporal path, Steiner Tree is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely Min. Aged Steiner Labeling (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number |R| of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL remains NP-hard, it is in FPT with respect to the number |R| of terminals. That is, adding the age restriction, makes the above problems strictly harder (unless P=NP or W[1]=FPT).

Cite as

Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The Complexity of Computing Optimum Labelings for Temporal Connectivity. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{klobas_et_al:LIPIcs.MFCS.2022.62,
  author =	{Klobas, Nina and Mertzios, George B. and Molter, Hendrik and Spirakis, Paul G.},
  title =	{{The Complexity of Computing Optimum Labelings for Temporal Connectivity}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.62},
  URN =		{urn:nbn:de:0030-drops-168603},
  doi =		{10.4230/LIPIcs.MFCS.2022.62},
  annote =	{Keywords: Temporal graph, graph labeling, foremost temporal path, temporal connectivity, Steiner Tree}
}
Document
The Complexity of Transitively Orienting Temporal Graphs

Authors: George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe, Kleinberg, Kumar, JCSS, 2002], the individual time-labeled edges remain undirected: an edge e = {u,v} with time-label t specifies that "u communicates with v at time t". This is a symmetric relation between u and v, and it can be interpreted that the information can flow in either direction. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior in various situations. An orientation of a temporal graph is called temporally transitive if, whenever u has a directed edge towards v with time-label t₁ and v has a directed edge towards w with time-label t₂ ≥ t₁, then u also has a directed edge towards w with some time-label t₃ ≥ t₂. If we just demand that this implication holds whenever t₂ > t₁, the orientation is called strictly temporally transitive, as it is based on the fact that there is a strict directed temporal path from u to w. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph 𝒢 is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether 𝒢 is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.

Cite as

George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The Complexity of Transitively Orienting Temporal Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.MFCS.2021.75,
  author =	{Mertzios, George B. and Molter, Hendrik and Renken, Malte and Spirakis, Paul G. and Zschoche, Philipp},
  title =	{{The Complexity of Transitively Orienting Temporal Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{75:1--75:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.75},
  URN =		{urn:nbn:de:0030-drops-145157},
  doi =		{10.4230/LIPIcs.MFCS.2021.75},
  annote =	{Keywords: Temporal graph, transitive orientation, transitive closure, polynomial-time algorithm, NP-hardness, satisfiability}
}
Document
Computing Maximum Matchings in Temporal Graphs

Authors: George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e,t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ ℕ is given. The requirement that a vertex cannot be matched twice in any Δ-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.

Cite as

George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing Maximum Matchings in Temporal Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.STACS.2020.27,
  author =	{Mertzios, George B. and Molter, Hendrik and Niedermeier, Rolf and Zamaraev, Viktor and Zschoche, Philipp},
  title =	{{Computing Maximum Matchings in Temporal Graphs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.27},
  URN =		{urn:nbn:de:0030-drops-118881},
  doi =		{10.4230/LIPIcs.STACS.2020.27},
  annote =	{Keywords: Temporal Graph, Link Stream, Temporal Line Graph, NP-hardness, APX-hardness, Approximation Algorithm, Fixed-parameter Tractability, Independent Set}
}
Document
A Parameterized Complexity View on Collapsing k-Cores

Authors: Junjie Luo, Hendrik Molter, and Ondrej Suchý

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)


Abstract
We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. [AAAI 2017] and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r >=0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k <=2 and k >= 3. For the latter case it is known that for all x >= 0 Collapsed k-Core is W[P]-hard when parameterized by b. We show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b+x) if k <=2. Furthermore, we show that Collapsed k-Core is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.

Cite as

Junjie Luo, Hendrik Molter, and Ondrej Suchý. A Parameterized Complexity View on Collapsing k-Cores. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.IPEC.2018.7,
  author =	{Luo, Junjie and Molter, Hendrik and Such\'{y}, Ondrej},
  title =	{{A Parameterized Complexity View on Collapsing k-Cores}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.7},
  URN =		{urn:nbn:de:0030-drops-102088},
  doi =		{10.4230/LIPIcs.IPEC.2018.7},
  annote =	{Keywords: r-Degenerate Vertex Deletion, Feedback Vertex Set, Fixed-Parameter Tractability, Kernelization Lower Bounds, Graph Algorithms, Social Network Analysis}
}
Document
Finding Secluded Places of Special Interest in Graphs

Authors: René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.

Cite as

René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:LIPIcs.IPEC.2016.5,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Mertzios, George B. and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej},
  title =	{{Finding Secluded Places of Special Interest in Graphs}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.5},
  URN =		{urn:nbn:de:0030-drops-69380},
  doi =		{10.4230/LIPIcs.IPEC.2016.5},
  annote =	{Keywords: Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set}
}
Document
06431 Working Group Summary: Atomicity in Mobile Networks

Authors: Sebastian Obermeier, Joos-Hendrik Böse, Stefan Böttcher, Panos Kypros Chrysanthis, Alex Delis, Le Gruenwald, Anirban Mondal, Aris Ouksel, George Samaras, and Stratis Viglas

Published in: Dagstuhl Seminar Proceedings, Volume 6431, Scalable Data Management in Evolving Networks (2007)


Abstract
We introduce different mobile network applications and show to which degree the concept of database transactions is required within the applications. We show properties of transaction processing and explain which properties are important for each of the mobile applications. Furthermore, we discuss open questions regarding transaction processing in mobile networks and identify open problems for further research.

Cite as

Sebastian Obermeier, Joos-Hendrik Böse, Stefan Böttcher, Panos Kypros Chrysanthis, Alex Delis, Le Gruenwald, Anirban Mondal, Aris Ouksel, George Samaras, and Stratis Viglas. 06431 Working Group Summary: Atomicity in Mobile Networks. In Scalable Data Management in Evolving Networks. Dagstuhl Seminar Proceedings, Volume 6431, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{obermeier_et_al:DagSemProc.06431.4,
  author =	{Obermeier, Sebastian and B\"{o}se, Joos-Hendrik and B\"{o}ttcher, Stefan and Chrysanthis, Panos Kypros and Delis, Alex and Gruenwald, Le and Mondal, Anirban and Ouksel, Aris and Samaras, George and Viglas, Stratis},
  title =	{{06431 Working Group Summary: Atomicity in Mobile Networks}},
  booktitle =	{Scalable Data Management in Evolving Networks},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6431},
  editor =	{Stefan B\"{o}ttcher and Le Gruenwald and Pedro Jose Marr\'{o}n and Evaggelia Pitoura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06431.4},
  URN =		{urn:nbn:de:0030-drops-9521},
  doi =		{10.4230/DagSemProc.06431.4},
  annote =	{Keywords: Mobile ad noc networks, mobile databases, mobile transactions, atomicity}
}
Document
06431 Working Group Summary: P2P, Ad Hoc and Sensor Networks – All the Different or All the Same?

Authors: Peter A. Boncz, Angela Bonifati, Joos-Hendrik Böse, Stefan Böttcher, Panos Kypros Chrysanthis, Le Gruenwald, Arantza Illarramendi, Peter Janacik, Birgitta König-Ries, Wolfgang May, Anirban Mondal, Sebastian Obermeier, Aris Ouksel, and George Samaras

Published in: Dagstuhl Seminar Proceedings, Volume 6431, Scalable Data Management in Evolving Networks (2007)


Abstract
Currently, data management technologies are in the process of finding their way into evolving networks, i.e. P2P, ad hoc and wireless sensor networks. We examine the properties, differences and commonalities of the different types of evolving networks, in order to enable the development of adequate technologies suiting their characteristics. We start with presenting definitions for the different network types, before arranging them in a network hierarchy, to gain a clear view of the area. Then, we analyze and compare the example applications for each of the types using different design dimensions. Based on this work, we finally present a comparison of P2P, ad hoc and wireless sensor networks.

Cite as

Peter A. Boncz, Angela Bonifati, Joos-Hendrik Böse, Stefan Böttcher, Panos Kypros Chrysanthis, Le Gruenwald, Arantza Illarramendi, Peter Janacik, Birgitta König-Ries, Wolfgang May, Anirban Mondal, Sebastian Obermeier, Aris Ouksel, and George Samaras. 06431 Working Group Summary: P2P, Ad Hoc and Sensor Networks – All the Different or All the Same?. In Scalable Data Management in Evolving Networks. Dagstuhl Seminar Proceedings, Volume 6431, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{boncz_et_al:DagSemProc.06431.5,
  author =	{Boncz, Peter A. and Bonifati, Angela and B\"{o}se, Joos-Hendrik and B\"{o}ttcher, Stefan and Chrysanthis, Panos Kypros and Gruenwald, Le and Illarramendi, Arantza and Janacik, Peter and K\"{o}nig-Ries, Birgitta and May, Wolfgang and Mondal, Anirban and Obermeier, Sebastian and Ouksel, Aris and Samaras, George},
  title =	{{06431 Working Group Summary: P2P, Ad Hoc and Sensor Networks – All the Different or All the Same?}},
  booktitle =	{Scalable Data Management in Evolving Networks},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6431},
  editor =	{Stefan B\"{o}ttcher and Le Gruenwald and Pedro Jose Marr\'{o}n and Evaggelia Pitoura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06431.5},
  URN =		{urn:nbn:de:0030-drops-9514},
  doi =		{10.4230/DagSemProc.06431.5},
  annote =	{Keywords: P2P, ad hoc, wireless sensor networks, database systems}
}
Document
04441 Working Group - Some Open Aspects of Mobile Ad-hoc NETwork, Peer-to-Peer, and Self-organizing Systems

Authors: Joos-Hendrik Böse, Stefan Böttcher, Le Gruenwald, Pedro Jóse Marrón, Philipp Obreiter, Evaggelia Pitoura, Peter Reiher, Kai-Uwe Sattler, and Frank Seliger

Published in: Dagstuhl Seminar Proceedings, Volume 4441, Mobile Information Management (2005)


Abstract
This document summarizes the results of the working group discussion on Mobile Ad-hoc NETworks (MANETs), peer-to-peer (p2p) and self-organizing systems held at the workshop on Mobile Information Management in October 2

Cite as

Joos-Hendrik Böse, Stefan Böttcher, Le Gruenwald, Pedro Jóse Marrón, Philipp Obreiter, Evaggelia Pitoura, Peter Reiher, Kai-Uwe Sattler, and Frank Seliger. 04441 Working Group - Some Open Aspects of Mobile Ad-hoc NETwork, Peer-to-Peer, and Self-organizing Systems. In Mobile Information Management. Dagstuhl Seminar Proceedings, Volume 4441, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{bose_et_al:DagSemProc.04441.3,
  author =	{B\"{o}se, Joos-Hendrik and B\"{o}ttcher, Stefan and Gruenwald, Le and Marr\'{o}n, Pedro J\'{o}se and Obreiter, Philipp and Pitoura, Evaggelia and Reiher, Peter and Sattler, Kai-Uwe and Seliger, Frank},
  title =	{{04441 Working Group - Some Open Aspects of Mobile Ad-hoc NETwork, Peer-to-Peer, and Self-organizing Systems}},
  booktitle =	{Mobile Information Management},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4441},
  editor =	{Margaret H. Dunham and Birgitta K\"{o}nig-Ries and Evaggelia Pitoura and Peter Reiher and Can T\"{u}rker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04441.3},
  URN =		{urn:nbn:de:0030-drops-2171},
  doi =		{10.4230/DagSemProc.04441.3},
  annote =	{Keywords: MANET, P2P}
}
Document
04441 Working Group – Research Issues in Mobile Transactions

Authors: Joos-Hendrik Böse, Stefan Böttcher, Le Gruenwald, Evaggelia Pitoura, Peter Reiher, George Samaras, Thomas Schwarz, and Can Türker

Published in: Dagstuhl Seminar Proceedings, Volume 4441, Mobile Information Management (2005)


Abstract
This document discusses three scenarios for databases with mobile clients, summarizes typical applications and requirements for each of the three scenarios, and outlines the open research issues which should be solved within each of the three scenarios. While the first scenario consists of mobile clients that are connect to a wired network, the second scenario consists of a network of mobile clients with a single-hop distance to each other but without a wired network, and the third scenario considers a network of mobile clients some of which are in multi-hop distance.

Cite as

Joos-Hendrik Böse, Stefan Böttcher, Le Gruenwald, Evaggelia Pitoura, Peter Reiher, George Samaras, Thomas Schwarz, and Can Türker. 04441 Working Group – Research Issues in Mobile Transactions. In Mobile Information Management. Dagstuhl Seminar Proceedings, Volume 4441, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{bose_et_al:DagSemProc.04441.7,
  author =	{B\"{o}se, Joos-Hendrik and B\"{o}ttcher, Stefan and Gruenwald, Le and Pitoura, Evaggelia and Reiher, Peter and Samaras, George and Schwarz, Thomas and T\"{u}rker, Can},
  title =	{{04441 Working Group – Research Issues in Mobile Transactions}},
  booktitle =	{Mobile Information Management},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4441},
  editor =	{Margaret H. Dunham and Birgitta K\"{o}nig-Ries and Evaggelia Pitoura and Peter Reiher and Can T\"{u}rker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04441.7},
  URN =		{urn:nbn:de:0030-drops-1685},
  doi =		{10.4230/DagSemProc.04441.7},
  annote =	{Keywords: Transactions , mobile clients , multi-hop wireless networks}
}
  • Refine by Author
  • 5 Molter, Hendrik
  • 4 Böse, Joos-Hendrik
  • 4 Böttcher, Stefan
  • 4 Gruenwald, Le
  • 4 Mertzios, George B.
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Graph algorithms analysis
  • 2 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 2 Feedback Vertex Set
  • 2 NP-hardness
  • 2 P2P
  • 2 Temporal graph
  • 1 APX-hardness
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 2 2005
  • 2 2007
  • 1 2017
  • 1 2019
  • 1 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail