Type
Now showing items 120 of 33

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 
Bchromatic number: Beyond NPhardness
(Dagstuhl Publishing, 2015)The bchromatic number of a graph G, chi_b(G), is the largest integer k such that G has a kvertex 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 ECCbased Grouping Proofs for Rfids
(The author, 2012)Recently, a new privacypreserving 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 semicomplete 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 semicomplete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, ...Conference object 
Connecting Vertices by Independent Trees
(Schloss Dagstuhl – LeibnizZentrum 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, 20040713)Component software is software that has been assembled from various pieces of standardized, reusable computer programs, socalled 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 – LeibnizZentrum 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 NPhard, 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 Fillin and Treewidth. We discover unexpected ...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 OutTrees with Many Leaves
(Dagstuhl Publishing, 2009)The {\sc $k$Leaf OutBranching} problem is to find an outbranching, 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 Fillin of Sparse Graphs: Kernelization and Approximation
(Dagstuhl Publishing, 2011)The Minimum Fillin 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 
A New Generating Set Search Algorithm for Partially Separable Functions
(IARIA, 2010)A new derivativefree optimization method for unconstrained optimization of partially separable functions is presented. Using average curvature information computed from sampled function values the method generates an ...Peer reviewedConference object 
NonConstructivity in Kan Simplicial Sets
(Dagstuhl Publishing, 2015)We give an analysis of the nonconstructivity of the following basic result: if X and Y are simplicial sets and Y has the Kan extension property, then Y X also has the Kan extension property. By means of Kripke countermodels ...Conference object