Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2

The problem of finding two disjoint Hamiltonian cycles of minimum sum weight is considered in a complete undirected graph with arbitrarily chosen weights of the edges 1 and 2. The main result of the paper is the presentation of polynomial algorithms with the currently best guaranteed performance factors 26/21 and 6/5. These algorithms are based on finding the partial tours with a large number of edges in the graphs of a special type.     

The irregularity strength and cost of the union of cliques

Assign positive integer weights to the edges of a simple graph with no component isomorphic to K₁ or K₂, in such a way that the graph becomes irregular, i.e., the weight sums at the vertices become pairwise distinct. The minimum of the largest weights assigned over all such irregular assignments on the vertex-disjoint union of complete graphs is determined. The method of proof also yields the smallest possible total increase in the sum of edge weights in irregular asignments, called irregularity cost.     

Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.     

The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks

In this paper, we consider a new edge colouring problem motivated by wireless mesh networks optimization: the proportional edge colouring problem. Given a graph G with positive weights associated to its edges, we want to find a proper edge colouring which assigns to each edge at least a proportion (given by its weight) of all the colours. If such colouring exists, we want to find one using the minimum number of colours. We proved that deciding if a weighted graph admits a proportional edge colouring is polynomial while determining its proportional edge chromatic number is NP-hard. We also give a lower and an upper bound that can be polynomially computed. We finally characterize some graphs and weighted graphs for which we can determine the proportional edge chromatic number.     

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.     

Register Allocation in Structured Programs

In this article we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we show that when attention is restricted tostructured programswhich we define to be programs whose control-flow graphs are series-parallel, there is an efficient algorithm that produces a solution which is within a factor of 2 of the optimal solution. We note that even with the previous restriction the resulting coloring problem is NP-complete.We also consider how to delete a minimum number of edges from arbitrary control-flow graphs to make them series-parallel and to apply our algorithm. We show that this problem is Max SNP hard. However, we define the notion of anapproximate articulation pointand we give efficient algorithms to find approximate articulation points. We present a heuristic for the edge deletion problem based on this notion which seems to work well when the given graph is close to series-parallel.     

Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function.     

On the edge multicoloring of unicyclic graphs

A multicoloring of an edge weighted graph is an assignment of intervals to its edges so that the intervals of adjacent edges do not intersect at interior points and the length of each interval is equal to the weight of the edge. The minimum length of the union of all intervals is called an edge multichromatic number of the graph. The maximum weighted degree of a vertex (i.e., the sum of the weights of all edges incident with it) is an evident lower bound of this number. There are available the examples in which the multichromatic number is one and a half times larger than the lower bound. Also, there is a conjecture that the bound cannot exceeded by a larger factor. Here we prove this conjecture for the class of unicyclic graphs.     

On heavy paths in 2-connected weighted graphs

A weighted graph is a graph in which every edge is assigned a non-negative real number. In a weighted graph, the weight of a path is the sum of the weights of its edges, and the weighed degree of a vertex is the sum of the weights of the edges incident with it. In this paper we give three weighted degree conditions for the existence of heavy or Hamilton paths with one or two given end-vertices in 2-connected weighted graphs.     

Partial inverse maximum spanning tree in which weight can only be decreased under $$l_p$$-norm

The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm.     

Matching interdiction

We introduce two interdiction problems involving matchings, one dealing with edge removals and the other dealing with vertex removals. Given is an undirected graph G with positive weights on its edges. In the edge interdiction problem, every edge of G has a positive cost and the task is to remove a subset of the edges constrained to a given budget, such that the weight of a maximum matching in the resulting graph is minimized. The vertex interdiction problem is analogous to the edge interdiction problem, with the difference that vertices instead of edges are removed. Hardness results are presented for both problems under various restrictions on the weights, interdiction costs and graph classes. Furthermore, we study the approximability of the edge and vertex interdiction problem on different graph classes. Several approximation-hardness results are presented as well as two constant-factor approximations, one of them based on iterative rounding. A pseudo-polynomial algorithm for solving the edge interdiction problem on graphs with bounded treewidth is proposed which can easily be adapted to the vertex interdiction problem. The algorithm presents a general framework to apply dynamic programming for solving a large class of problems in graphs with bounded treewidth. Additionally, we present a method to transform pseudo-polynomial algorithms for the edge interdiction problem into fully polynomial approximation schemes, using a scaling and rounding technique.     

On the complexity of rainbow spanning forest problem

Given a graph \(G=(V,E,L)\) and a coloring function \(\ell : E \rightarrow L\), that assigns a color to each edge of G from a finite color set L, the rainbow spanning forest problem (RSFP) consists of finding a rainbow spanning forest of G such that the number of components is minimum. A spanning forest is rainbow if all its components (trees) are rainbow. A component whose edges have all different colors is called rainbow component. The RSFP on general graphs is known to be NP-complete. In this paper we use the 3-SAT Problem to prove that the RSFP is NP-complete on trees and we prove that the problem is solvable in polynomial time on paths, cycles and if the optimal solution value is equal to 1. Moreover, we provide an approximation algorithm for the RSFP on trees and we show that it approximates the optimal solution within 2.     

分裂图的区间图完全化问题（英文）

The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.     

Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem

We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian cycle problem (HCP) in an undirected graph of order $n$ . Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph’s edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly $n$ snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic uses transformations inspired by $k$ -opt algorithms such as the, now classical, Lin–Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in $n^3$ major iterations.     

Some properties of graphs determined by edge zeta functions

In 1989, Hashimoto introduced an edge zeta function of a finite graph, which is a generalization of the Ihara zeta function. The edge zeta function is the reciprocal of a polynomial in twice as many indeterminants as edges in the graph and can be computed via a determinant expression. We look at graph properties which we can determine using the edge zeta function. In particular, the edge zeta function is enough to deduce the clique number, the number of Hamiltonian cycles, and whether a graph is perfect or chordal. Finally, we present a new example illustrating that the Ihara zeta function cannot necessarily do the same.     

Color degree and monochromatic degree conditions for short properly colored cycles in edge‐colored graphs

For an edge‐colored graph, its minimum color degree is defined as the minimum number of colors appearing on the edges incident to a vertex and its maximum monochromatic degree is defined as the maximum number of edges incident to a vertex with a same color. A cycle is called properly colored if every two of its adjacent edges have distinct colors. In this article, we first give a minimum color degree condition for the existence of properly colored cycles, then obtain the minimum color degree condition for an edge‐colored complete graph to contain properly colored triangles. Afterwards, we characterize the structure of an edge‐colored complete bipartite graph without containing properly colored cycles of length 4 and give the minimum color degree and maximum monochromatic degree conditions for an edge‐colored complete bipartite graph to contain properly colored cycles of length 4, and those passing through a given vertex or edge, respectively.     

Edge-Colorings of 4-Regular Graphs with the Minimum Number of Palettes

A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Horňák, Kalinowski, Meszka and Wo?niak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs. In particular, we show that certain values of the palette index imply the existence of an even cycle decomposition of size 3 (a partition of the edge-set of a graph into 3 2-regular subgraphs whose connected components are cycles of even length). This result can be extended to 4d-regular graphs. Moreover, in studying the palette index of a 4-regular graph, the following problem arises: does there exist a 4-regular graph whose even cycle decompositions cannot have size smaller than 4?     

On the Maximum Weight of a Sparse Connected Graph of Given Order and Size

The weight of an edge of a graph is defined to be the sum of degrees of vertices incident to the edge. The weight of a graph G is the minimum of weights of edges of G. Jendrol’ and Schiermeyer (Combinatorica 21:351–359, 2001) determined the maximum weight of a graph having n vertices and m edges, thus solving a problem posed in 1990 by Erd?s. The present paper is concerned with a modification of the mentioned problem, in which involved graphs are connected and of size \(m\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) -\left( {\begin{array}{c}\lceil n/2\rceil \\ 2\end{array}}\right) \).     

On the effect of major vertices on the number of light edges

This paper presents an inequality satisfied by planar graphs of minimum degree five. For the purposes of this paper, an edge of a graph is light if the weight of the edge, or the sum of the degrees of the vertices incident with it, is at most eleven. The inequality presented shows that planar graphs of minimum degree five have a large number of light edges. This inequality improves upon a recent inequality of Borodin and Sanders, which showed that 7/15 times the number of edges of weight 10 plus 1/5 times the number of edges of weight 11 is at least 12. These constants 7/15 and 1/5 were shown to be best possible. The inequality in this paper shows that, for this type of graph, the presence of vertices of degree at least eight increases the number of light edges. A graph is presented which shows that the coefficient obtained for the number of degree eight vertices is best possible. © 1996 John Wiley & Sons, Inc.     

Optimally super-edge-connected transitive graphs

Let X=(V,E) be a connected regular graph. X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ′(X) of X is the minimum number of edges whose removal disconnects X into non-trivial components. A super-edge-connected k-regular graph is said to be optimally super-edge-connected if its restricted edge connectivity attains the maximum 2k−2. In this paper, we define the λ′-atoms of graphs with respect to restricted edge connectivity and show that if X is a k-regular k-edge-connected graph whose λ′-atoms have size at least 3, then any two distinct λ′-atoms are disjoint. Using this property, we characterize the super-edge-connected or optimally super-edge-connected transitive graphs and Cayley graphs. In particular, we classify the optimally super-edge-connected quasiminimal Cayley graphs and Cayley graphs of diameter 2. As a consequence, we show that almost all Cayley graphs are optimally super-edge-connected.