Algorithms and Methods for Solving Scheduling Problems and Other Extremum Problems on Large-Scale Graphs

Autor:	A. M. Chepovskiy, S. V. Chernyshev, E. V. Pankratiev, E. A. Cherepanov
Rok vydání:	2005
Předmět:	Statistics and Probability Discrete mathematics Applied Mathematics General Mathematics Mixed graph Directed graph Strength of a graph law.invention Combinatorics law Graph power Line graph Cycle graph Null graph Algorithm Complement graph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Journal of Mathematical Sciences. 128:3487-3495
ISSN:	1573-8795 1072-3374
Popis:	We consider a large-scale directed graph G = (V, E) whose edges are endowed with a family of characteristics. A subset of vertices of the graph, V′ ⊂ V, is selected and some additional conditions are imposed on these vertices. An algorithm for reducing the optimization problem on the graph G to an optimization problem on the graph G′ = (V′, E′) of a lower dimension is developed. The main steps of the solution and some methods for constructing an approximate solution to the problem on the transformed graph G′ are presented.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::306e79d870e9e99a9a4c0698dbba39d7 https://doi.org/10.1007/s10958-005-0283-z Zobrazit plný text záznamu Plný text ve formátu PDF