Recent Submissions

  • Fast and accurate CNN-based brushing in scatterplots 

    Fan, Chaoran; Hauser, Helwig (Journal article; Peer reviewed, 2018)
    Brushing plays a central role in most modern visual analytics solutions and effective and efficient techniques for data selection are key to establishing a successful human‐computer dialogue. With this paper, we address ...
  • Quantitative Externalization of Visual Data Analysis Results Using Local Regression Models 

    Matkovic, Kresimir; Abraham, Hrvoje; Jelovic, Mario; Hauser, Helwig (Journal article; Peer reviewed, 2017)
    Both interactive visualization and computational analysis methods are useful for data studies and an integration of both approaches is promising to successfully combine the benefits of both methodologies. In interactive ...
  • Bisection of Bounded Treewidth Graphs by Convolutions 

    Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E. (Journal article; Peer reviewed, 2019)
    In the Bisection problem, we are given as input an edge-weighted graph G. The task is to find a partition of V(G) into two parts A and B such that ||A| - |B|| <= 1 and the sum of the weights of the edges with one endpoint ...
  • Personalized Sketch-Based Brushing in Scatterplots 

    Fan, Chaoran; Hauser, Helwig (Journal article; Peer reviewed, 2019)
    Brushing is at the heart of most modern visual analytics solutions and effective and efficient brushing is crucial for successful interactive data exploration and analysis. As the user plays a central role in brushing, ...
  • Complexity of the Steiner Network Problem with Respect to the Number of Terminals 

    Eiben, Eduard; Knop, Dusan; Panolan, Fahad; Suchý, Ondřej (Journal article; Peer reviewed, 2019)
    In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subseteq V(G) with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H ...
  • On KDE-based brushing in scatterplots and how it compares to CNN-based brushing 

    Fan, Chaoran; Hauser, Helwig (Chapter, 2019)
    In this paper, we investigate to which degree the human should be involved into the model design and how good the empirical model can be with more careful design. To find out, we extended our previously published Mahalanobis ...
  • Parameterized complexity classification of deletion to list matrix-partition for low-order matrices 

    Agrawal, Akanksha; Kolay, Sudeshna; Madathil, Jayakrishnan; Saurabh, Saket (Journal article; Peer reviewed, 2019)
    Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G) - > 2^{[l]} (where [l] = {1,2,...,l}), a list M-partition of G with respect to L is a partition of V(G) into l parts, ...
  • Balanced judicious bipartition is fixed-parameter tractable 

    Lokshtanov, Daniel; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
    The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of ...
  • Packing cycles faster than Erdos-Posa 

    Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
    The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention ...
  • Rank vertex cover as a natural problem for algebraic compression 

    Meesum, Syed Mohammad; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
    The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a long-standing, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and ...
  • Packing arc-disjoint cycles in tournaments 

    Bessy, Stephane; Bougeret, Marin; Krithika, R; Sahu, Abhishek; Saurabh, Saket; Thiebaut, Jocelyn; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
    A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining ...
  • Parameterized complexity of conflict-free matchings and paths 

    Agrawal, Akanksha; Jain, Pallavi; Kanesh, Lawqueen; Saurabh, Saket (Journal article; Peer reviewed, 2019)
    An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) ...
  • Connecting the Dots (with Minimum Crossings) 

    Agrawal, Akanksha; Guspiel, Grzegorz; Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
    We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ...
  • Parameterized streaming algorithms for min-ones d-SAT 

    Agrawal, Akanksha; Bonnet, Édouard; Curticapean, Radu; Miltzow, Tillmann; Saurabh, Saket; Biswas, Arindam; Brettell, Nick; Marx, Dániel; Raman, Venkatesh (Journal article; Peer reviewed, 2019)
    In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has ...
  • Approximation algorithms in combinatorial scientific computing 

    Pothen, Alex; Ferdous, SM; Manne, Fredrik (Journal article; Peer reviewed, 2019)
    We survey recent work on approximation algorithms for computing degreeconstrained subgraphs in graphs and their applications in combinatorial scientific computing. The problems we consider include maximization versions of ...
  • Robust Independent Validation of Experiment and Theory: Rivet version 3 

    Bierlich, Christian; Buckley, Andy; Butterworth, J. M.; Corpe, L.; Grellscheid, David; Gütschow, C.; Karczmarczyk, P.; Klein, J.; Lönnblad, Leif; Pollard, C. S.; Schulz, Holger; Siegert, Frank (Journal article; Peer reviewed, 2020)
    First released in 2010, the Rivet library forms an important repository for analysis code, facilitating comparisons between measurements of the final state in particle collisions and theoretical calculations of those final ...
  • High-Dimensional Bayesian Network Inference From Systems Genetics Data Using Genetic Node Ordering 

    Wang, Lingfei; Audenaert, Pieter; Michoel, Tom Luk Robert (Journal article; Peer reviewed, 2019)
    Studying the impact of genetic variation on gene regulatory networks is essential to understand the biological mechanisms by which genetic variation causes variation in phenotypes. Bayesian networks provide an elegant ...
  • Multiscale Visual Drilldown for the Analysis of Large Ensembles of Multi-Body Protein Complexes 

    Furmanová, Katarína; Jurčík, Adam; Kozlíková, Barbora; Hauser, Helwig; Byska, Jan (Journal article; Peer reviewed, 2020)
    When studying multi-body protein complexes, biochemists use computational tools that can suggest hundreds or thousands of their possible spatial configurations. However, it is not feasible to experimentally verify more ...
  • Visual Analysis of Ligand Trajectories in Molecular Dynamics 

    Jurcik, Adam; Furmanova, Katarina; Byska, Jan; Vonasek, Vojtech; Vavra, Ondrej; Ulbrich, Pavol; Hauser, Helwig; Kozlikova, Barbora (Journal article; Peer reviewed, 2019)
    In many cases, protein reactions with other small molecules (ligands) occur in a deeply buried active site. When studying these types of reactions, it is crucial for biochemists to examine trajectories of ligand motion. ...
  • Exact and approximate digraph bandwidth 

    Jain, Pallavi; Kanesh, Lawqueen; Lochet, William; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2019)
    In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of ...

View more