Egon Wanke

TCS Journal 2016 Journal Article

A linear time algorithm for metric dimension of cactus block graphs

• Stefan Hoffmann
• Alina Elterman
• Egon Wanke

An undirected graph G = ( V, E ) has metric dimension at most k if there is a vertex set U ⊆ V such that | U | ≤ k and ∀ u, v ∈ V, u ≠ v, there is a vertex w ∈ U such that d G ( w, u ) ≠ d G ( w, v ), where d G ( u, v ) is the distance (the length of a shortest path in an unweighted graph) between u and v. The metric dimension of G is the smallest integer k such that G has metric dimension at most k. A cactus block graph is an undirected graph whose biconnected components are either cycles or complete graphs. We present a linear time algorithm for computing the metric dimension of cactus block graphs.

TCS Journal 2016 Journal Article

Directed NLC-width

• Frank Gurski
• Egon Wanke
• Eda Yilmaz

In this paper we generalize the concept of NLC-width introduced by Wanke in [39] to directed graphs. We show bounds of this new width parameter for directed graphs and relationships between directed NLC-width and directed clique-width which was introduced by Courcelle and Olariu in [8]. We also compare the measures with their undirected versions of the underlying undirected graphs. Our results imply that computing the directed NLC-width of a directed graph is NP-hard. Further we consider the directed width of digraph classes. We show that the set of directed co-graphs equals the set of graphs of directed NLC-width 1, while the set of directed co-graphs is characterized, by excluding two digraphs, as a proper subset of the set of all graphs of directed clique-width 2, which is a remarkable difference to the undirected versions of the graphs. From an algorithmic point of view directed NLC-width is a powerful digraph parameter, since for every digraph problem expressible in monadic second order logic with quantifications over vertices and vertex sets ( MSO 1 -logic) there exists an fpt-algorithm with respect to the parameter directed NLC-width (of the input digraph). We show how the tree structure of directed NLC-width expressions can be used to solve a lot of further hard digraph problems efficiently on graphs of bounded width. We apply our method in order to give xp-algorithms for the problems Directed Hamiltonian Path, Directed Hamiltonian Cycle, Directed Cut, and Regular Subdigraph with respect to the parameter directed NLC-width. For most of these problems this is best possible, since they are known to be fixed-parameter intractable with respect to the parameter directed NLC-width.

YNIMG Journal 2009 Journal Article

Optimization of cortical hierarchies with continuous scales and ranges

• Andrew T. Reid
• Antje Krumnack
• Egon Wanke
• Rolf Kötter

Although information flow in the neocortex has an apparent hierarchical organization, there is much ambiguity with respect to the definition of such a hierarchy, particularly in higher cortical regions. This ambiguity has been addressed by utilizing observable anatomical criteria, based upon tract tracing experiments, to constrain the definition of hierarchy [Felleman D. J. and van Essen D. C. , 1991. Distributed hierarchical processing in the primate. Cereb. Cortex. 1(1), 1–47. ]. There are, however, a high number of equally optimal hierarchies that fit these constraints [Hilgetag C. C. , O'Neill M. A. , Young M. P. , 1996. Indeterminate organization of the visual system. Science. 271(5250), 776–777. ]. Here, we propose a refined constraint set for optimization which utilizes continuous, rather than discrete, hierarchical levels, and permits a range of acceptable values rather than attempting to fit fixed hierarchical distances. Using linear programming to obtain hierarchies across a number of range sizes, we find a clear hierarchical pattern for both the original and refined versions of the Felleman and Van Essen [Felleman D. J. and van Essen D. C. , 1991. Distributed hierarchical processing in the primate. Cereb. Cortex. 1(1), 1–47. ] visual network. We also obtain an optimal hierarchy from a refined set of anatomical criteria which allows for the direct specification of hierarchical distance from the laminar distribution of labelled cells (Barone P. , Batardiere A. , Knoblauch K. , Kennedy H. , 2000. Laminar distribution of neurons in extrastriate areas projecting to visual areas V1 and V4 correlates with the hierarchical rank and indicates the operation of a distance rule. J. Neurosci. 20(9), 3263–3281.), and discuss the limitations and further possible refinements of such an approach.

TCS Journal 2006 Journal Article

Vertex disjoint paths on clique-width bounded graphs

• Frank Gurski
• Egon Wanke

We show that the l vertex disjoint paths problem between l pairs of vertices can be solved in linear time for co-graphs but is NP-complete for graphs of clique-width at most 6 and NLC-width at most 4. The NP-completeness follows from the fact that the line graph of a graph of tree-width k has clique-width at most 2 k + 2 and NLC-width at most k + 2, and a result by Nishizeki et al. [The edge-disjoint paths problem is NP-complete for series-parallel graphs, Discrete Appl. Math. 115 (2001) 177–186]. The vertex disjoint paths problem is the first graph problem shown to be NP-complete on graphs of bounded clique-width but solvable in linear time on co-graphs and graphs of bounded tree-width. Additionally, we show that the r vertex disjoint paths problem between each of l pairs of vertices can be solved in polynomial time for co-graphs, if l is given to the input, and for graphs of bounded clique-width, if l is fixed.

TCS Journal 2005 Journal Article

On the relationship between NLC-width and linear NLC-width

• Frank Gurski
• Egon Wanke

In this paper, we consider NLC-width, NLCT-width, and linear NLC-width bounded graphs. We show that the set of all complete binary trees has unbounded linear NLC-width and that the set of all co-graphs has unbounded NLCT-width. Since trees have NLCT-width 3 and co-graphs have NLC-width 1, it follows that the family of linear NLC-width bounded graph classes is a proper subfamily of the family of NLCT-width bounded graph classes and that the family of NLCT-width bounded graph classes is a proper subfamily of the family of NLC-width bounded graph classes.

MFCS Conference 2001 Conference Paper

A 3-Approximation Algorithm for Movement Minimization in Conveyor Flow Shop Processing

• Wolfgang Espelage
• Egon Wanke

Abstract We consider the movement minimization problem in a conveyor flow shop processing controlled by one worker for all machines. A machine can only execute tasks if the worker is present. Each machine can serve as a buffer for exactly one job. The worker has to cover a certain distance to move from one machine to the next or previous one. The objective is to minimize the total distance the worker has to cover for the processing of all jobs. We introduce the first polynomial time approximation algorithm for this problem with a performance bounded by some fixed factor.

SODA Conference 2000 Conference Paper

Movement minimization in conveyor flow shop processing

• Wolfgang Espelage
• Egon Wanke

I&C Journal 1997 Journal Article

The Bounded Degree Problem for eNCE Graph Grammars

• Konstantin Skodinis
• Egon Wanke

The complexity of the bounded degree problem is analyzed for graph languages generated by eNCE graph grammars. In particular, the bounded degree problem is shown to be undecidable for eNCE graph grammars, DEXPTIME-complete for confluent/boundary eNCE graph grammars, PSPACE-complete for linear eNCE graph grammars, and P-complete for non-blocking eNCE graph grammars. In our main theorem we show that the bounded degree problem is NL-complete for reduced non-blocking eNCE graph grammars. Many of the shown results carry over to other types of graph grammars.

MFCS Conference 1993 Conference Paper

Paths and Cycles in Finite Periodic Graphs

• Egon Wanke

Abstract We consider finite periodic graphs G m defined by nonnegative integer vectors m and directed graphs G whose edges are labeled with integer vector-weights. G m has a vertex ( u, x ) for each vertex u of G and each nonnegative integer vector x less than or equal to m. G m has an edge from ( u, x ) to ( v, x + z ) if and only if G has an edge from u to v with vector weight z. We analyze the complexity and present algorithms for finding paths and cycles in finite periodic graphs. The present paper shows that path and cycle problems on finite periodic graphs are PSPACE-complete under various restrictions, but solvable in polynomial time if the vector weights of the edges are bounded.

SODA Conference 1993 Conference Paper

Polynomial Algorithms for Minimum Cost Paths in Periodic Graphs

• Franz Höfting
• Egon Wanke

I&C Journal 1991 Journal Article

Algorithms for graph problems on BNLC structured graphs

• Egon Wanke

We present algorithms for analyzing single graphs and sets of graphs generated by boundary node label controlled (BNLC) graph grammars. This paper extends a unified framework for developing algorithms on context-free graph languages to BNLC graph languages. Graphs in BNLC graph languages do not necessarily have vertex separators of bounded size as do graphs in context-free graph languages. We give combinatorial decision and query algorithms on single graphs generated by a deterministic BNLC graph grammar and algorithms for the following question: Does the language of a given BNLC graph grammar contain a graph that fulfills a certain graph property? All algorithms developed in this paper consider the graph grammar as input.