Finding Maximum Induced Matchings in Subclasses of Claw-Free and <Emphasis Type="Italic">P</Emphasis><Subscript>5</Subscript>-Free Graphs,and in Graphs with Matching and Induced Matching of Equal Maximum Size

In a graph G a matching is a set of edges in which no two edges have a common endpoint. An induced matching is a matching in which no two edges are linked by an edge of G. The maximum induced matching (abbreviated MIM) problem is to find the maximum size of an induced matching for a given graph G. This problem is known to be NP-hard even on bipartite graphs or on planar graphs. We present a polynomial time algorithm which given a graph G either finds a maximum induced matching in G, or claims that the size of a maximum induced matching in G is strictly less than the size of a maximum matching in G. We show that the MIM problem is NP-hard on line-graphs, claw-free graphs, chair-free graphs, Hamiltonian graphs and r-regular graphs for r \geq 5. On the other hand, we present polynomial time algorithms for the MIM problem on (P ₅,D _m )-free graphs, on (bull, chair)-free graphs and on line-graphs of Hamiltonian graphs.     

Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition

Abstract. Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in can be solved in polynomial time. We show that if C is a class of graphs that are modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the treewidth and the minimum fill-in on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms that use respectively O(n) and O(n ³ ) time for treewidth and minimum fill-in.     

On the exploitation of CDF based wireless scheduling

Channel-aware scheduling strategies – such as the CDF scheduler (CS) algorithm – provide an effective mechanism for utilizing the channel data rate for improving throughput performance in wireless data networks by exploiting channel fluctuations. A highly desired property of such a scheduling strategy is that its algorithm is stable, in the sense that no user has incentive “cheating” the algorithm in order to increase his/hers channel share (on the account of others). Considering a single user we show that no such user can increase his/hers channel share by misreporting the channel capacity. In contrast, considering a group of users, we present a scheme by which coordination allows them to gain permanent increase in both their time slots share and in their throughput at the expense of others, by misreporting their rates. We show that for large populations consisting of regular and coordinated users in equal numbers, the ratio of allocated time slots between a coordinated and a regular user converges to e − 1 ≈ 1.7. Our scheme targets the very fundamental principle of CS (as opposed to just attacking implementation aspects), which bases its scheduling decisions on the Cumulative Distribution Function (CDF) of the channel rates reported by users. Our scheme works both for the continuous channel spectrum and the discrete channel spectrum versions of the problem. Finally, we outline a modified CDF scheduler immune to such attacks.     

Abstract Effective Models

We modify Gurevich's notion of abstract machine so as to encompass computational models, that is, sets of machines that share the same domain. We also add an effectiveness requirement. The resultant class of “Effective Models” includes all known Turing-complete state-transition models, operating over any countable domain.     

Path-matching problems

The notion of matching in graphs is generalized in this paper to a set of paths rather than to a set of edges. The generalized problem, which we call thepath-matching problem, is to pair the vertices of an undirected weighted graph such that the paths connecting each pair are subject to certain objectives and/or constraints. This paper concentrates on the case where the paths are required to be edge-disjoint and the objective is to minimize the maximal cost of a path in the matching (i.e., the bottleneck version). Other variations of the problem are also mentioned. Two algorithms are presented to find the best matching under the constraints listed above for trees. Their worst-case running times areO(n logd logw), whered is the maximal degree of a vertex,w is the maximal cost of an edge, andn is the size of the tree, andO(n ²), respectively. The problem is shown to be NP-complete for general graphs. Applications of these problems are also discussed.Udi Manber was supported in part by an NSF Presidential Young Investigator Award (Grant DCR-8451397), with matching funds from AT&T.     

细线条自动光学检查所面临的挑战及解决方法

制作高密度互连衬底依靠细线条印刷电路板技术,这种技术带来了非常严格的类似线间距变窄到50～15μm时的成品率问题。几何图形、形状、材料和表面抛光有关的细线条面板对光学检查提出了新的挑战,需要新的方法来保证可靠的检查。这种挑战是由生产因素产生的,例如导体线条的高宽比、在半添加加工中电镀线条的拱形顶部、有光泽或半透明的薄片和嵌入式无源元件等。其他的挑战来自物理和光学极限,即对于非常小的细线条缺陷需要达到很高的放大倍率才能查出。     

Novel EIS postprocessing algorithm for breast cancer diagnosis

A new postprocessing algorithm was developed for the diagnosis of breast cancer using electrical impedance scanning. This algorithm automatically recognizes bright focal spots in the conductivity map of the breast. Moreover, this algorithm discriminates between malignant and benign/normal tissues using two main predictors: phase at 5 kHz and crossover frequency, the frequency at which the imaginary part of the admittance is at its maximum. The thresholds for these predictors were adjusted using a learning group consisting of 83 carcinomas and 378 benign cases. In addition, the algorithm was verified on an independent test group including 87 carcinomas, 153 benign cases and 356 asymptomatic cases. Biopsy was used as gold standard for determining pathology in the symptomatic cases. A sensitivity of 84% and a specificity of 52% were obtained for the test group.     

Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition

Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in can be solved in polynomial time. We show that if C is a class of graphs that are modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the treewidth and the minimum fill-in on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms that use respectively O(n) and O(n3) time for treewidth and minimum fill-in.     

Pierce point minimization and optimal torch path determination in flame cutting

This paper addresses the problem of sequencing a torch for the cutting of a stock sheet nested with regular or irregular parts. The image of the nesting is reduced to an equivalent graph, and the objective is to traverse this graph with a minimum number of pierce points, or blowthroughs. If the graph has $\text{2k}$ vertices of odd degree, then $\text{k}$ pierce points are necessary and sufficient to traverse the graph. The torch path problem formulation includes manufacturing cost, efficiency, and distortion considerations. We present three algorithms for the problem. The first algorithm shows how to determine the $\text{k}$ torch paths, and is optimal in run time complexity. The second algorithm uses trim margin edges to investigate further reduction in the number of pierce points. The third algorithm guarantees that for the special case where a torch path has no vertices of odd degree, no piece will be dropped that needs further interior cuts. Some possible extensions to this work are also addressed.