1,721,064 research outputs found
A Polynomial Characterization of Some Graph Partitioning Problems
No full textThe Uniform Partition (UP) and the Simple Max Partition (SMP) problems are NP-complete graph partitioning problems, and polynomial-time algorithms are known for few classes of graphs only. In the present paper, the class of line-graphs is considered and a polynomial algorithm is proposed to solve both problems in this class. A similar result can be obtained extending the class to digraphs
A Polynomial Algorithm for Partitioning Line-graphs
No full textTwo NP-complete unweighted graph partitioning problems are considered: Simple Max Partitioning (SMP) and Uniform Graph Partitioning (UGP). For both problems, polynomial-time algorithms are available for special classes of graphs. In the present paper, the class of line-graphs is considered and a polynomial algorithm is proposed to solve both UGP and SMP in this class
The Lazy Cook Problem, or Scheduling Two Parallel Machines to Optimize Vehicle Utilization
No full textA cook has to prepare n cakes using an oven with two racks. According to the recipe, the i-th cake has to be baked for exactly ai minutes. Cakes to be cooked are taken from a table and carried to the oven, and
once cooked are carried back to the table by means of a trolley that can carry two cakes at a time. What is the
minimum number q* of round trips required of the cook? This problem has application to the operation scheduling
of transportation systems and to material cutting. A different problem arises according to whether the cook accepts or not to stay near the oven for awhile with the trolley. If the trolley cannot be idle at the oven, an optimum schedule with no oven idle-time always exists: consequently, the trolley schedule is trivial, and the problem is transformed
into a set packing. For this case, we propose and test a heuristic method which generates all of the promising
columns of the set packing, and solves the resulting problem by branch-and-bound. Instead, if the trolley can be
idle at the oven for a limited amount of time, a problem arises to find an optimal schedule of the trolley: in this case we show how to use a scaling technique in order to obtain a very good feasible solution by the method above
Recent Contributions of OR to Network Optimization, feature issue of the European J. of Operational Research
No full text
Polynomial Algorithms for Special Cases of the Balanced Bipartite Subgraph Problem
No full textA balanced bipartite graph is a bipartite graph (U,V,E) such that |U|=|V|. Balanced bipartite subgraphs problems arise in such fields as VLSI design and flexible manufaturing. An example is the following: given a graph G and a positive integer m, does G contain a balanced complete bipartite subgraph with at least 2m vertices? This problem is NP-complete for several classes of graphs, including bipartite. We contribute to characterize "easy" classes and individuate properties useful to develop solution algorithms for the general case. A simple polynomial algorithm can be devised for bipartite graphs with no induced P5 on the basis of a result of Bacsò and Tuza. We generalize the result to particular subclasses of (i) graphs wth no odd cycles of given size, (ii) paw-free graphs, (iii)diamndo-free graphs
- …
