Search

This is the second paper in a series of two. The goal of the series is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time-algorithm that starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a P6-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem. [ABSTRACT FROM AUTHOR]

Task planning involves automating the creation of the routes for vessels with known coordinates in a confined space. The management of vessel release in a given area affects the time required for a vessel to complete its voyage, and maximizing vessel performance involves identifying the shortest route. A key issue in automating the generation of the optimal (shortest) routes is selecting the appropriate mathematical apparatus. This paper considers an optimization method based on a recursive algorithm using Bellman-Ford routing tasks for large dimensions. Unlike other optimization techniques, the proposed method enables the shortest path to be assessed in a network model with a complex topology, even if there are arcs with negative weights. The practical implementation of the modified Floyd algorithm was demonstrated using a sample automated build and using it to calculate a network model with a complex topology, using an iterative procedure for a program prepared in MATLAB. Implementation of the computer model is simple, and unlike existing models, it eliminates restrictions associated with the presence of negative weights and cycles on a network and automates search shortcuts in ground branch functional means in MATLAB. To confirm the accuracy of the obtained results, we performed an example calculation using the network. The proposed algorithm and recursive procedure are recommended for finding energy-efficient solutions during the management of mobile objects on waterways. [ABSTRACT FROM AUTHOR]