Distributed approach for solving time-dependent problems in multimodal transport networks.
Dominating sets of random 2-in 2-out directed graphs.
Domination numbers in graphs with removed edge or set of edges
It is known that the removal of an edge from a graph G cannot decrease a domination number γ(G) and can increase it by at most one. Thus we can write that γ(G) ≤ γ(G-e) ≤ γ(G)+1 when an arbitrary edge e is removed. Here we present similar inequalities for the weakly connected domination number and the connected domination number , i.e., we show that and if G and G-e are connected. Additionally we show that and if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected...
Drawing 3-polytopes with good vertex resolution.
Drawing clustered graphs on an orthogonal grid.
Drawing graphs on two and three lines.
Drawing graphs within graphs.
Edge-coloring and -coloring for various classes of graphs.
Edge-disjoint paths in permutation graphs
In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.
Efficient algorithms for minimal disjoint path problems on chordal graphs
Disjoint paths have applications in establishing bottleneck-free communication between processors in a network. The problem of finding minimum delay disjoint paths in a network directly reduces to the problem of finding the minimal disjoint paths in the graph which models the network. Previous results for this problem on chordal graphs were an O(|V| |E|²) algorithm for 2 edge disjoint paths and an O(|V| |E|) algorithm for 2 vertex disjoint paths. In this paper, we give an O(|V| |E|) algorithm for...
Elimination of local bridges
Embedding vertices at points: Few bends suffice for planar graphs.
Encodings of cladograms and labeled trees.
Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs.
Equivalence of compositional expressions and independence relations in compositional models
We generalize Jiroušek’s (right) composition operator in such a way that it can be applied to distribution functions with values in a “semifield“, and introduce (parenthesized) compositional expressions, which in some sense generalize Jiroušek’s “generating sequences” of compositional models. We say that two compositional expressions are equivalent if their evaluations always produce the same results whenever they are defined. Our first result is that a set system is star-like with centre if...
Erratum: Equivalence of compositional expressions and independence relations in compositional models
Evaluating a weighted graph polynomial for graphs of bounded tree-width.
Experimental comparison of 2-satisfiability algorithms
Experimental comparison of graph drawing algorithms for cubic graphs.
Experiments with the fixed-parameter approach for two-layer planarization.