Search results for: COMBINATORIAL BOUND - Bridge of Knowledge

Search

Search results for: COMBINATORIAL BOUND

Search results for: COMBINATORIAL BOUND

  • Database of the estimations of the numbers of simplices of triangulation of some classical Lie groups

    Open Research Data
    open access
    • X. Zhao
    • W. Marzantowicz
    • G. Graff
    • H. Duan

    It is know that any smooth manifold can be triangulated. The number of simplices of triangulation of a given manifold depends on its topological and combinatorial structure. The data consists of the lower bounds for the numbers of simplices of each dimension of any triangulation of classical Lie groups U(n), SU(n), Sp(n), and SO(n) for n up to 25. Each...

  • Estimates for minimal number of periodic points for smooth self-maps of simply-connected manifolds

    Open Research Data
    open access

    We consider a closed smooth connected and simply-connected manifold of dimension at least 4 and its self-map f. The topological invariant Dr[f] is equal to the minimal number of r-periodic points in the smooth homotopy class of f. We assume that r is odd and all coefficients b(k) of so-called periodic expansion of Lefschetz numbers of iterations are...

  • Normal-form preemption sequences for an open problem in scheduling theory

    Publication

    - JOURNAL OF SCHEDULING - Year 2016

    Structural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems,...

    Full text to download in external service

  • Computational aspects of greedy partitioning of graphs

    In this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...

    Full text available to download

  • Minimal double dominating sets in trees

    Publication

    - Year 2014

    We provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.

  • An algorithm for listing all minimal double dominating sets of a tree

    Publication

    We provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.

    Full text to download in external service