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.
Extending the MAX Algorithm for Maximum Independent Set
The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.