In this paper we introduce the concept of a boundary class, which is a helpful tool for classification of hereditary classes of graphs according to the complexity of the independent set problem. It ...is shown that in a class
X
defined by a finite set of forbidden induced subgraphs, the problem is NP-hard if and only if
X
includes a boundary class. The paper presents a particular boundary class and establishes several new polynomially solvable cases for the independent set problem.
The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems ...restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called “critical” graph classes, which play an important role in the complexity analysis for the family. Recent progress in studying such classes is presented in the article.
We discuss the effectiveness of integer programming for solving large instances of the independent set problem. Typical LP formulations, even strengthened by clique inequalities, yield poor bounds ...for this problem. We show that a strong bound can be obtained by the use of the so-called rank inequalities, which generalize the clique inequalities. For some problems the clique inequalities imply the rank inequalities, and then a strong bound is guaranteed already by the simpler formulation.
Technologies for heterogeneous integration have been promoted as an option to drive innovation in the semiconductor industry. However, adoption by designers is lagging behind and market shares are ...still low. Alongside the lack of appropriate design tools, high manufacturing costs are one of the main reasons. Micro-transfer printing (μTP) is a novel and promising micro-assembly technology that enables the heterogeneous integration of dies originating from different wafers. This technology uses an elastomer stamp to transfer dies in parallel from source wafers to their target positions, indicating a high potential for reducing manufacturing time and cost. In order to achieve the latter, the geometrical interdependencies between source, target and stamp and the resulting wafer utilization must be considered during design. We propose an approach to evaluate a given μTP design with regard to the manufacturing costs. We achieve this by developing a model that integrates characteristics of the assembly process into the cost function of the design. Our approach can be used as a template how to tackle other assembly-related co-design issues - addressing an increasingly severe cost optimization problem of heterogeneous systems design.
The Maximum Weight Independent Set (MWIS) Problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated problem on ...graphs, it is well known to be NP-complete and hard to approximate. Several graph classes for which MWIS can be solved in polynomial time have been introduced in the literature. This note shows that MWIS can be solved in polynomial time for (P6,co-banner)-free graphs – where a P6 is an induced path of 6 vertices and a co-banner is a graph with vertices a,b,c,d,e and edges ab,bc,cd,ce,de – so extending different analogous known results for other graph classes, namely, P4-free, 2K2-free, (P5,co-banner)-free, and (P6,triangle)-free graphs. The solution algorithm is based on an idea/algorithm of Farber (1989) 10, leading to a dynamic programming approach for MWIS, and needs none of the aforementioned known results as sub-procedure.
► The note deals with the Maximum Weight Independent Set (MWIS) Problem. ► It shows that MWIS can be efficiently solved for (P6,co-banner)-free graphs. ► It extends different analogous known results for other graph classes. ► It needs none of the aforementioned known results as sub-procedure. ► It is based on a previous idea of Martin Farber.
Graph theory is a key subject for both mathematics and computer science. It is used for modelling many problems such as maximal independent set, minimum covering and matching. In our study, we have ...extended the previous work on placing materials that may react with each other on a 2-D warehouse. We have modelled the problem using graph theory. Then, we have developed extensions on the heuristic algorithm which is using Paull-Unger method that finds Maximal Independent Sets. First two of these extensions include finding solutions with gaps for specific graphs, and meanwhile capability of performing replacement in any desired rectangle surface. The last and most effective extension is pruning unnecessary backtracking steps with the help of smarter heuristics in the algorithm.
PDF
