New results on generalized graph coloring.
Nombre de sauts et graphes série-parallèles
Nondeterminism versus determinism of finite automata over directed acyclic graphs.
NP-completeness of minimal width unordered tree layout.
NP-completeness of the planar separator problems.
NP-completeness results for minimum planar spanners.
NP-hardness results for intersection graphs
Numbering action vertices in workflow graphs
Workflow graphs, consisting of actions, events, and logical switches, are used to model business processes. In order to easily identify the actions within a workflow graph, it is useful to number them in such a way that the numbering reflects the structure of the workflow. However, available tools offer only rudimental numbering schemes. In the paper, a set of natural requirements is defined that a logical numbering should fulfill. It is investigated under what conditions there is an appropriate...
Numerical studies of the asymptotic height distribution in binary search trees.
On a code problem concerning planar acyclic graphs
On a generalization of perfect -matching
The paper is concerned with the existence of non-negative or positive solutions to , where is the vertex-edge incidence matrix of an undirected graph. The paper gives necessary and sufficient conditions for the existence of such a solution.
On bandwidth, cutwidth, and quotient graphs
On computing the distinguishing numbers of trees and forests.
On external-memory planar depth first search.
On -pairable graphs from trees
The concept of the -pairable graphs was introduced by Zhibo Chen (On -pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter , called the pair length of a graph , as the maximum such that is -pairable and if is not -pairable for any positive integer . In this paper, we answer the two open questions raised by Chen in the case that the graphs involved...
On linear layouts of graphs.
On locating a single path-like facility in a general graph
On location problems on fuzzy graphs.
Location problems concern a wide set of fields where it is usually assumed that exact data are known. However, in real applications, the location of the facility considered can be full of linguistic vagueness, that can be appropriately modeled using networks with fuzzy values. In that way arise Fuzzy Location Problems; this paper deals with their general formulation and the description solution methods. Namely we show the variety of problems that can be considered in this context and, for some of...
On Minimum and Maximum Spanning Trees of Linearly Moving Points.
On planar mixed hypergraphs.