The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
An equitable coloring of a graph is a proper coloring such that the sizes of color classes are as even as possible. An m-bounded coloring of a graph is a proper coloring such that the sizes of color classes are all bounded by a preassigned number m. Formulas for the equitable and m-bounded chromatic numbers of a split graph are established in this paper. It is proved that split graphs satisfy the...
In this paper, we present some results on maximal planar graphs with minimum degree five, denoted by MPG5 graphs [6]. We consider a subset of MPG5 graphs, called the $$\mathcal{Z}$$ graphs, for which all vertices of degree superior to five are not adjacent. We give a vertex four coloring for every $$\mathcal{Z}$$ graph.
In this paper, we propose an algorithm for finding all the edge colorings in bipartite graphs. Our algorithm requires O(T(n, m, Δ)+K min{n2+m,T(n,m,Δ)}) time and O(mΔ) space, where n denotes the number of vertices, m denotes the number of edges, Δ denotes the number of maximum degree, T(n,m,Δ) denotes the time complexity of an edge coloring algorithm, and K denotes the number of edge colorings.
Since the invention of PQ-trees by Booth and Lueker in 1976 the recognition of interval graphs has been simplified dramatically. In [7], we presented a very simple linear-time recognition algorithm based on scanning vertices arranged in a special perfect elimination ordering. Our approach is to decompose a given interval graph into uniquely representable components whose models can be obtained by...
We consider the collection of all spanning trees of a graph with distance between them based on the size of the symmetric difference of their edge sets. A central spanning tree of a graph is one for which the maximal distance to all other spanning trees is minimal. We prove that the problem of constructing a central spanning tree is algorithmically difficult and leads to an NP-complete problem.
For an integer n≥3, the crown Sn0 is defined to be the graph with vertex set {a1, a2, ..., an, b1, b2, ..., bn} and edge set {aibj: 1≤i,j≤n,i≠j}. We consider the decomposition of the edges...
We prove (in two different ways) that in a sufficiently large tournament a vertex of outdegree at least two is always the beginning of an antidirected hamiltonian path starting with a forward arc. The proofs yield algorithms to find, if possible, an antidirected Hamiltonian path starting in a given vertex with an arc of a given direction. The first proof yields the theorem for all tournaments of order...
The conditions under which both graph G and its complement ¯G share some common properties, e.g., with diameter 2, with ℓ1-addressings, with property of being strongly regular are studied. Many examples and counterexamples from different areas of graph theory regarding them are provided. In particular, a census of graphs with at most six vertices is given.
The double description method is a simple and useful algorithm for enumerating all extreme rays of a general polyhedral cone in ℝd, despite the fact that we can hardly state any interesting theorems on its time and space complexities. In this paper, we reinvestigate this method, introduce some new ideas for efficient implementations, and show some empirical results indicating its practicality in solving...
We survey and present new geometric and combinatorial properties, of some polyhedra with application in combinatorial optimization, for example, the max-cut and multicommodity flow problems. Namely we consider the volume, symmetry group, facets, vertices, face lattice, diameter, adjacency and incidence relations and connectivity of the metric polytope and its relatives. In particular, using its large...
Task intervals were defined in [CL94] for disjunctive scheduling so that, in a scheduling problem, one could derive much information by focusing on some key subsets of tasks. The advantage of this approach was to shorten the size of search trees for branch&bound algorithms because more propagation was performed at each node. In this paper, we refine the propagation scheme and describe in...
Given an n×n×n array C=(cijk) of real numbers, the three-dimensional axial bottleneck assignment problem (3-BAP) is to find two permutations φ and ψ of {1, ..., n} such that maxi=1,...,n ciφ(i)ψ(i) is minimized. We first present two closely related conditions on the cost array C, the wedge property and the weak wedge property, which...
In this paper, we are interested in combinatorial problems of graph and hypergraph colouring linked to Ramsey's theorem. We construct correct colourings for the edges of these graphs and hypergraphs, by stochastic optimization algorithms in which the criterion of minimization is the number of monochrome cliques. To avoid local optima, we propose a technique consisting of an enumeration of edge colourings...
A recent model of neural networks, named the Hybrid Neural Network Model (HN), for solving optimization problems appeared in [3]. In [3], the main algorithm called the Hybrid Network Updating Algorithm (HNUA) is used to drive the HN model. The best thing about the HNUA is that it reaches a feasible solution very quickly. Our argument here is that while the HNUA is very quick to satisfy the constraints,...
We apply in the case of the maximum independent set, a general thought process consisting in integrating an information on the optimal objective value in its instance. This thought process for the study of the relative hardness between determining solutions of combinatorial optimization problems and computing (approximately or exactly) their optimal values, allows us to define classes of independent...
Weakly greedy algorithm is an extension of the greedy algorithm. It gives a solution of a combinatorial optimization problem on discrete systems in a properly wider class than the class of Δ-matroids. Discrete systems with a certain 2 to 2 exchangeability belong to this class. We characterize these systems in terms of their rank function. Excluded minors of Δ-matroids and these systems are also described.
Seymour [10] has characterized graphs and more generally matroids in which the simplest possible necessary condition, the “cut condition”, is also sufficient for multiflow feasibility. In this work we exhibit the next level of necessary conditions, three conditions which correspond in a well-defined way to minimally non-ideal binary clutters. We characterize the subclass of matroids where the presented...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.