An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure (Q1073717): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Gottfried Tinhofer / rank | |||
Property / reviewed by | |||
Property / reviewed by: M. A. Frumkin / rank | |||
Property / author | |||
Property / author: Gottfried Tinhofer / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: M. A. Frumkin / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0377-2217(85)90034-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1995478410 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5636912 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal design of centralized computer networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3671757 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rational solutions of the graphsack problem / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 13:32, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure |
scientific article |
Statements
An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure (English)
0 references
1985
0 references
The authors consider a special linear programming problem. Constraints of the problem are in natural correspondence with paths from the root to leaves in a tree. For solving the problem they propose an algorithm with runs in time \(O(n^ 2)\), where n is the number of leaves in the tree. The algorithm has run time O(n log n) for balanced trees.
0 references
simplex algorithm
0 references
tree structure
0 references