Now showing items 1-20 of 35

• #### Approximating Acyclicity Parameters of Sparse Hypergraphs ﻿

(Dagstuhl Publishing, 2009)
The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ...
Conference object
• #### B-chromatic number: Beyond NP-hardness ﻿

(Dagstuhl Publishing, 2015)
The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ...
Conference object
• #### Colluding Tags Attack on the ECC-based Grouping Proofs for Rfids ﻿

(The author, 2012)
Recently, a new privacy-preserving elliptic curve based grouping proof protocol with colluding tag prevention( CTP) has been proposed. The CTP protocol is claimed to be resistant against colluding tags attacks in which ...
Conference object
• #### Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings ﻿

(Dagstuhl Publishing, 2013)
The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, ...
Conference object
• #### Connecting Vertices by Independent Trees ﻿

(Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2014)
We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ...
Conference object
• #### Counting Instances of Software Components ﻿

(University of Bergen, Department of Informatics, 2004-07-13)
Component software is software that has been assembled from various pieces of standardized, reusable computer programs, so-called components. Executing component software creates instances of these components. For several ...
Conference object
• #### Direct data transfer between SOAP web services in Orchestration ﻿

(ACM, 2012)
In scientific data analysis, workflows are used to integrate and coordinate resources such as databases and tools. Workflows are normally executed by an orchestrator that invokes component services and mediates data ...
Conference object
• #### Editing to Eulerian Graphs ﻿

(Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2014)
We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and ...
Conference object
• #### Enumerating minimal connected dominating sets in graphs of bounded chordality ﻿

(Dagstuhl Publishing, 2015)
Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration ...
Conference object
• #### Fast biclustering by dual parameterization ﻿

(Dagstuhl Publishing, 2015)
We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none ...
Conference object
• #### Finding even subgraphs even faster ﻿

(Dagstuhl Publishing, 2015)
Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k ...
Conference object
• #### Finding Induced Subgraphs via Minimal Triangulations ﻿

(Dagstuhl Publishing, 2010)
Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems in- cluding Minimum Fill-in and Treewidth. We discover unexpected ...
Conference object
• #### Finding k Disjoint Triangles in an Arbitrary Graph ﻿

(Springer Verlag, 2004)
Conference object
• #### Interactive Visualization of Streaming Data with Kernel Density Estimation ﻿

(IEEE, 2011)
In this paper, we discuss the extension and integration of the statistical concept of Kernel Density Estimation (KDE) in a scatterplotlike visualization for dynamic data at interactive rates. We present a line kernel ...
Conference object
• #### Investigating Streamless Sets ﻿

(Dagstuhl Publishing, 2015)
In this paper we look at streamless sets, recently investigated by Coquand and Spiwack. A set is streamless if every stream over that set contain a duplicate. It is an open question in constructive mathematics whether the ...
Conference object
• #### Investigating the Limitations of Java Annotations for Input Validation ﻿

(2010)
Recently Java annotations have received a lot of attention as a possible way to simplify the usage of various frameworks, ranging from persistence and verification to security. In this paper we discuss our experiences ...
Conference object
• #### Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves ﻿

(Dagstuhl Publishing, 2009)
The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint ...
Conference object
• #### Maximum matching width: New characterizations and a fast algorithm for dominating set ﻿

(Dagstuhl Publishing, 2015)
We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A ...
Conference object
• #### Minimum Fill-in of Sparse Graphs: Kernelization and Approximation ﻿

(Dagstuhl Publishing, 2011)
The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop ...
Conference object
• #### Model Checking Healthcare Workflows Using Alloy ﻿

(Elsevier B.V., 2014)
Workflows are used to organize business processes, and workflow management tools are used to guide users in which order these processes should be performed. These tools increase organizational efficiency and enable users ...
Conference object