Zobrazeno 1 - 10
of 58
pro vyhledávání: '"Hartung, Sepp"'
Autor:
van Bevern, René, Bredereck, Robert, Chopin, Morgan, Hartung, Sepp, Hüffner, Falk, Nichterlein, André, Suchý, Ondřej
Publikováno v:
Discrete Applied Mathematics 220:134-160, 2017
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 2009] as DAG Partitioning: given an arc-weighted directed acyclic graph on $n$ vertices and $m$ arcs, delete arcs with total weight at
Externí odkaz:
http://arxiv.org/abs/1611.08809
Co-clustering, that is, partitioning a numerical matrix into homogeneous submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-
Externí odkaz:
http://arxiv.org/abs/1512.05693
Publikováno v:
Operations Research Letters 42(4):290--292, 2014
Given an undirected graph with edge costs and edge demands, the Capacitated Arc Routing problem (CARP) asks for minimum-cost routes for equal-capacity vehicles so as to satisfy all demands. Constant-factor polynomial-time approximation algorithms wer
Externí odkaz:
http://arxiv.org/abs/1404.3660
Motivated by a strongly growing interest in anonymizing social network data, we investigate the NP-hard Degree Anonymization problem: given an undirected graph, the task is to add a minimum number of edges such that the graph becomes k-anonymous. Tha
Externí odkaz:
http://arxiv.org/abs/1402.6239
The NP-hard 2-Club problem is, given an undirected graph G=(V,E) and l\in N, to decide whether there is a vertex set S\subseteq V of size at least l such that the induced subgraph G[S] has diameter at most two. We make progress towards a systematic c
Externí odkaz:
http://arxiv.org/abs/1305.3735
Autor:
Hartung, Sepp, Nichterlein, André
The NP-hard Metric Dimension problem is to decide for a given graph G and a positive integer k whether there is a vertex subset of size at most k that separates all vertex pairs in G. Herein, a vertex v separates a pair {u,w} if the distance (length
Externí odkaz:
http://arxiv.org/abs/1211.1636
Autor:
Hartung, Sepp, Nichterlein, André
In graph realization problems one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match to the given sequence. This realization problem is known to be polynomial-time solvable when the graph is direc
Externí odkaz:
http://arxiv.org/abs/1110.1510
Autor:
Talmon, Nimrod, Hartung, Sepp
Publikováno v:
In Information and Computation October 2017 256:212-225
Autor:
van Bevern, René, Bredereck, Robert, Chopin, Morgan, Hartung, Sepp, Hüffner, Falk, Nichterlein, André, Suchý, Ondřej
Publikováno v:
In Discrete Applied Mathematics 31 March 2017 220:134-160
Autor:
Bazgan, Cristina, Bredereck, Robert, Hartung, Sepp, Nichterlein, André, Woeginger, Gerhard J.
Publikováno v:
In Theoretical Computer Science 4 April 2016 622:90-110