Now showing items 1-20 of 33

    • Approximating Acyclicity Parameters of Sparse Hypergraphs 

      Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (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 

      Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (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 

      Abyaneh, Mohammad Reza Sohizadeh (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 

      Pilipczuk, Michal Pawel (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 

      Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (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 

      Bezem, Marcus A.; Truong, Anh Hoang (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 

      Subramanian, Sattanathan; Sztromwasser, Paweł; Puntervoll, Pål; Petersen, Kjell (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 

      Dabrowski, Konrad K.; Golovach, Petr; van' t Hof, Pim; Paulusma, Daniël (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 

      Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (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 

      Drange, Pål Grønås; Reidl, Felix; Villaamil, Fernando Sánchez; Sikdar, Somnath (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 

      Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (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 

      Fomin, Fedor; Villanger, Yngve (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
    • Interactive Visualization of Streaming Data with Kernel Density Estimation 

      Lampe, Ove Daae; Hauser, Helwig (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 

      Parmann, Erik (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 

      Mancini, Federico; Hovland, Dag; Mughal, Khalid A. (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 

      Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve (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 

      Jeong, Jisu; Sæther, Sigve Hortemo; Telle, Jan Arne (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 

      Fomin, Fedor; Geevarghese, Philip; Villanger, Yngve (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
    • A New Generating Set Search Algorithm for Partially Separable Functions 

      Frimannslund, Lennart; Steihaug, Trond (IARIA, 2010)
      A new derivative-free 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
    • Non-Constructivity in Kan Simplicial Sets 

      Bezem, Marc; Coquand, Thierry; Parmann, Erik (Dagstuhl Publishing, 2015)
      We give an analysis of the non-constructivity 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