Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Heiko Schilling

dblp:s/HeikoSchilling · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
0since 2021 · last 2010
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
2 papers
Graph algorithms and graph theory · 68% Computational complexity · 23% Algorithms and data structures · 8%

Topics — the 6 heaviest of 7, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Graph algorithms and graph theory › graph cut
length-bounded cut
0.222010
Length-bounded cuts and flows · ACM Trans. Algorithms 2010
Length-Bounded Cuts and Flows · ICALP (1) 2006
Graph algorithms and graph theory
graph cut
0.112010
Length-bounded cuts and flows · ACM Trans. Algorithms 2010
Computational complexity
hardness of approximation
0.112010
Length-bounded cuts and flows · ACM Trans. Algorithms 2010
Graph algorithms and graph theory › graph algorithms › network flow
length-constrained flows
0.112010
Length-bounded cuts and flows · ACM Trans. Algorithms 2010
Graph algorithms and graph theory › graph algorithms
network flow
0.112010
Length-bounded cuts and flows · ACM Trans. Algorithms 2010
Computational complexity
parameterized complexity
0.112006
Length-Bounded Cuts and Flows · ICALP (1) 2006

Methods — techniques the papers use, named apart from their topics

approximation algorithm · 0.1NP-hardness reduction · 0.1
YearPublicationVenuePosition
2010 Length-bounded cuts and flows
abstract
For a given number L , an L -length-bounded edge-cut (node-cut, respectively) in a graph G with source s and sink t is a set C of edges (nodes, respectively) such that no s - t -path of length at most L remains in the graph after removing the edges (nodes, respectively) in C . An L -length-bounded flow is a flow that can be decomposed into flow paths of length at most L . In contrast to classical flow theory, we describe instances for which the minimum L -length-bounded edge-cut (node-cut, respectively) is Θ( n 2/3 )-times (Θ(√ n )-times, respectively) larger than the maximum L -length-bounded flow, where n denotes the number of nodes; this is the worst case. We show that the minimum length-bounded cut problem is NP -hard to approximate within a factor of 1.1377 for L ≥ 5 in the case of node-cuts and for L ≥ 4 in the case of edge-cuts. We also describe algorithms with approximation ratio O (min{ L , n/L }) ⊆ O √ n in the node case and O (min { L , n 2 / L 2 ,√ m } ⊆ O 2/3 in the edge case, where m denotes the number of edges. Concerning L -length-bounded flows, we show that in graphs with unit-capacities and general edge lengths it is NP -complete to decide whether there is a fractional length-bounded flow of a given value. We analyze the structure of optimal solutions and present further complexity results.
Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrác, Heiko Schilling, Martin Skutella
ACM Trans. Algorithms7
2006 Length-Bounded Cuts and Flows
Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Heiko Schilling, Martin Skutella
ICALP (1)5