|
|
|
|
|
Serafino Cicerone
Cicerone and Di Stefano defined and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. The defined graphs represent a generalization of...
ver más
|
|
|
|
|
|
|
|
|
Eirini Georgoulaki, Kostas Kollias and Tami Tamir
We study cost-sharing games in real-time scheduling systems where the server?s activation cost in every time slot is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positiv...
ver más
|
|
|
|
|
|
|
|
|
Vladimir Gurvich and Mikhail Vyalyi
We study the algorithmic complexity of solving subtraction games in a fixed dimension with a finite difference set. We prove that there exists a game in this class such that solving the game is EXP-complete and requires time 2O(??)
2
O
(
n
)
, where n is...
ver más
|
|
|
|
|
|
|
|
|
Sergey Kurapov,Maxim Davidovsky
Pág. 1 - 8
In general, a universal algorithm for testing a pair of graphs G and H for isomorphism exists. It is grounded on the fact that the rows and the corresponding columns of the adjacency matrix of the graph G can be rearranged until it turns into another, eq...
ver más
|
|
|
|
|
|
|
|
|
Joachim Niehren and Momar Sakho
We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions (????????
NREs
) from the usual XPath benchmark to nested word automata (????????
NWAs
). The determinizatio...
ver más
|
|
|
|