6 documents found

Article / Chapter
All rights reserved
2009-05-04

An Ω lower bound for computing the sum of even-ranked elements

Given a sequence A of 2n real numbers, the \ers\ problem asks for the sum of the n values that are at the even positions in the sorted order of the elements in A. We prove that, in the algebraic computation-tree model, this problem has time complexity \Theta(n \log n). This solves an open problem posed...
Article / Chapter
All rights reserved
2009-05-04

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G. We prove that it is NP complete to decide for a given chordal or chordal bipartite...
Article / Chapter
All rights reserved
2009-05-04

On the convexity number of graphs

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to...
Article / Chapter
All rights reserved
2009-05-04

On the hull number of triangle-free graphs

A set of vertices C in a graph is convex if it contains all vertices which lie on shortest paths between vertices in C. The convex hull of a set of vertices S is the smallest convex set containing S. The hull number h(G) of a graph G is the smallest cardinality of a set of vertices whose convex hull...

Availability

Type