Search

Abstract: In this paper, we define and analyze the nowhere dense classes of graphs. This notion is a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, classes with bounded expansion, to name just a few classes which are studied extensively in combinatorial and computer science contexts. In this paper, we show that this concept leads to a classification of general classes of graphs and to the dichotomy between nowhere dense and somewhere dense classes. This classification is surprisingly stable as it can be expressed in terms of the most commonly used basic combinatorial parameters, such as the independence number , the clique number , and the chromatic number . The remarkable stability of this notion and its robustness has a number of applications to mathematical logic, complexity of algorithms, and combinatorics. We also express the nowhere dense versus somewhere dense dichotomy in terms of edge densities as a trichotomy theorem. [Copyright &y& Elsevier]

Abstract: In this paper, we present algorithms that compute large matchings in planar graphs with fixed minimum degree. The algorithms give a guarantee on the size of the computed matching and run in linear time. Thus they are faster than the best known algorithm for computing maximum matchings in general graphs and in planar graphs, which run in and time, respectively. For the class of planar graphs with minimum degree 3, the bounds we achieve are known to be the best possible. Further, we discuss how minimum degree 5 can be used to obtain stronger bounds on the matching size. [Copyright &y& Elsevier]

Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [Copyright &y& Elsevier]

Abstract: We consider semistructured data as multirooted edge-labelled directed graphs, and path inclusion constraints on these graphs. A path inclusion constraint is satisfied by a semistructured data if any node reached by the regular query is also reached by the regular query . In this paper, two problems are mainly studied: the implication problem and the problem of the existence of a finite exact model. [–] We give a new decision algorithm for the implication problem of a constraint by a set of bounded path constraints where , , and the ’s are regular path expressions and the ’s are words, improving in this particular case, the more general algorithms of S. Abiteboul and V. Vianu, and N. Alechina et al. In the case of a set of word equalities , we provide a more efficient decision algorithm for the implication of a word equality , improving the more general algorithm of P. Buneman et al. We prove that, in this case, implication for nondeterministic models is equivalent to implication for (complete) deterministic ones. [–] We introduce the notion of exact model: an exact model of a set of path constraints satisfies the constraint if and only if this constraint is implied by . We prove that any set of constraints has an exact model and we give a decidable characterization of data which are exact models of bounded path inclusion constraints sets. [Copyright &y& Elsevier]