This study deals with the facility location problem of locating a set Vp of p facilities on a graph such that the subgraph induced by Vp is connected. We consider the connected p‐median problem on a cactus graph G whose vertices and edges have nonnegative weights. The aim of a connected p‐median problem is to minimize the sum of weighted distances from every vertex of a graph to the nearest vertex in Vp. We provide an O(n2p2) time algorithm for the connected p‐median problem, where n is the number of vertices.
Every graph G = (V, E) considered in this paper consists of a finite set V of vertices and a finite set E of edges, together with an incidence function that associates each edge e ∈ E of G with an unordered pair of vertices of G which are called the ends of the edge e. A graph is said to be a planar graph if it can be drawn in the plane so that its edges intersect only at their ends. A proper k‐vertex‐coloring of a graph G = (V, E) is a mapping c : V⟶S (S is a set of k colors) such that no two adjacent vertices are assigned the same colors. The famous Four Color Theorem states that a planar graph has a proper vertex‐coloring with four colors. However, the current known proof for the Four Color Theorem is computer assisted. In addition, the correctness of the proof is still lengthy and complicated. In 2010, a simple O(n2) time algorithm was provided to 4‐color a 3‐colorable planar graph. In this paper, we give an improved linear‐time algorithm to either output a proper 4‐coloring of G or conclude that G is not 3‐colorable when an arbitrary planar graph G is given. Using this algorithm, we can get the proper 4‐colorings of 3‐colorable planar graphs, planar graphs with maximum degree at most five, and claw‐free planar graphs.