Edge-disjoint Hamiltonian cycles in two-dimensional torus.
Effective reduction of Goresky-Kottwitz-MacPherson graphs.
Efficient, proximity-preserving node overlap removal.
Elimination of local bridges
Embedding complete ternary trees into hypercubes
We inductively describe an embedding of a complete ternary tree Tₕ of height h into a hypercube Q of dimension at most ⎡(1.6)h⎤+1 with load 1, dilation 2, node congestion 2 and edge congestion 2. This is an improvement over the known embedding of Tₕ into Q. And it is very close to a conjectured embedding of Havel [3] which states that there exists an embedding of Tₕ into its optimal hypercube with load 1 and dilation 2. The optimal hypercube has dimension ⎡(log₂3)h⎤ ( = ⎡(1.585)h⎤) or ⎡(log₂3)h⎤+1....
Embedding vertices at points: Few bends suffice for planar graphs.
Embeddings of hamiltonian paths in faulty k-ary 2-cubes
It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. Let (X,Y) be a bipartition of a k-ary 2-cube (even integer k ≥ 4). In this paper, we prove that for any two healthy vertices u ∈ X, v ∈ Y, there exists a hamiltonian path from u to v in the faulty k-ary 2-cube with one faulty vertex in each part.
Enumeration problems of trees. (Abzählprobleme bei Bäumen.)
Equi-partitioning of higher-dimensional hyper-rectangular grid graphs.
Errata : «Les hiérarchies de parties et leur demi-treillis»
Establishing Order in Planar Subdivisions.
Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées
Evaluating a weighted graph polynomial for graphs of bounded tree-width.
Even kernels.
Existence of feasible potentials on infinite networks.
Experiments with the fixed-parameter approach for two-layer planarization.
Exploiting the structure of conflict graphs in high level synthesis
In this paper we analyze the computational complexity of a processor optimization problem. Given operations with interval times in a branching flow graph, the problem is to find an assignment of the operations to a minimum number of processors. We analyze the complexity of this assignment problem for flow graphs with a constant number of program traces and a constant number of processors.
Extreme distances in multicolored point sets.