Counting maximal independent sets in directed path graphs

The problem of counting maximal independent sets is #P-complete for chordal graphs but solvable in polynomial time for its subclass of interval graphs. This work improves upon both of these results by showing that the problem remains #P-complete when restricted to directed path graphs but that a further restriction to rooted directed path graphs admits a polynomial time solution.     

Efficient algorithms for counting parameterized list H-colorings

We study the fixed parameter tractability of the counting version of a parameterization of the restrictive list H-coloring problem. The parameterization is defined by fixing the number of preimages of a subset C of the vertices in H through a weight assignment K on C. We show the fixed parameter tractability of counting the number of list (H,C,K)-colorings, for the case in which (H,C,K) is simple. We introduce the concept of compactor and a new algorithmic technique, compactor enumeration, that allow us to design fixed parameter algorithms for parameterized counting problems.     

On variable-weighted exact satisfiability problems

We show that the NP-hard optimization problems minimum and maximum weight exact satisfiability (XSAT) for a CNF formula C over n propositional variables equipped with arbitrary real-valued weights can be solved in O(||C||2^0.2441n ) time. To the best of our knowledge, the algorithms presented here are the first handling weighted XSAT optimization versions in non-trivial worst case time. We also investigate the corresponding weighted counting problems, namely we show that the number of all minimum, resp. maximum, weight exact satisfiability solutions of an arbitrarily weighted formula can be determined in O(n ²·||C||?+?2^0.40567n ) time. In recent years only the unweighted counterparts of these problems have been studied (Dahllöf and Jonsson, An algorithm for counting maximum weighted independent sets and its applications. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 292–298, 2002; Dahllöf et al., Theor Comp Sci 320: 373–394, 2004; Porschen, On some weighted satisfiability and graph problems. In: Proceedings of the 31st Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005). Lecture Notes in Comp. Science, vol. 3381, pp. 278–287. Springer, 2005).     

Algorithms for four variants of the exact satisfiability problem

We present four polynomial space and exponential time algorithms for variants of the E S problem. First, an O(1.1120ⁿ) (where n is the number of variables) time algorithm for the NP-complete decision problem of E 3-S , and then an O(1.1907ⁿ) time algorithm for the general decision problem of E S . The best previous algorithms run in O(1.1193ⁿ) and O(1.2299ⁿ) time, respectively. For the #P-complete problem of counting the number of models for E 3-S we present an O(1.1487ⁿ) time algorithm. We also present an O(1.2190ⁿ) time algorithm for the general problem of counting the number of models for E S ; presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix.     

基于Livermore模型CT图片构建人体躯干数字体模及其在肺部计数器虚拟刻度中的应用

基于Livermore 人体躯干物理模型CT图片构建数字体模,并结合蒙特卡罗程序MCNP对一套由四个宽能高纯锗探测器(BEGe)构成的肺部计数器进行了虚拟刻度.首先,利用点源(241Am,137Cs,60Co,54Mn,57Co,109Cd) 实验数据,对高纯锗晶体尺寸进行调整以获得正确的探测器几何参数,在γ射线能量13.9 keV～1332.5 keV范围内,调整后四个探测器全能峰效率实验测量的平均值与蒙特卡罗计算值的差别在±10%范围内.之后,对不同胸壁厚度(CWT=19 mm, 25 mm, 30 mm, 43 mm)躯干体模进行CT扫描获得其CT图片,利用Dosigray软件对CT图片进行分割后,连同探测器几何描述文件输入到OEDIPE软件,生成数字体模虚拟刻度用MCNP输入程序.最后,利用241Am、152Eu肺部源对数字体模虚拟刻度结果进行了实验验证,结果表明:在59.5 keV～1408 keV能量范围内,虚拟刻度结果与实验结果的差别在±10%之间;对于17.5 keV能量,差别在±30%之间.     

光电计数系统的研制

介绍了一种光电感应计数系统。它采用光源与计数器分立设计方式，光源采用半导体点光源激光发射器，计数器使用单片机系统。其电路简单、可靠，可以得出较为准确的参数。实验结果证明，该系统能达到较好的计数效果。     

Complexity results for structure-based causality

We give a precise picture of the computational complexity of causal relationships in Pearl's structural models, where we focus on causality between variables, event causality, and probabilistic causality. As for causality between variables, we consider the notions of causal irrelevance, cause, cause in a context, direct cause, and indirect cause. As for event causality, we analyze the complexity of the notions of necessary and possible cause, and of the sophisticated notions of weak and actual cause by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. We then analyze the complexity of the probabilistic notions of probabilistic causal irrelevance, likely causes of events, and occurrences of events despite other events. Moreover, we consider decision and optimization problems involving counterfactual formulas. To our knowledge, no complexity aspects of causal relationships in the structural-model approach have been considered so far, and our results shed light on this issue.     

New Results in Minimum-Comparison Sorting

We prove that sorting 13, 14 and 22 elements requires 34, 38 and 71 comparisons, respectively. This solves a long-standing problem posed by Knuth in his famous book The Art of Computer Programming, Volume 3, Sorting and Searching. The results are due to an efficient implementation of an algorithm for counting linear extensions of a given partial order. We also present some useful heuristics which allow us to decrease the running time of the implementation.     

DUVEX: An X-ray counting system based on YAG:Ce scintillator

A detector system, called DUVEX, has been developed for the soft-x-ray and extreme ultraviolet domain. It consists of a YAG:Ce scintillator coupled to a photomultiplier module working under vacuum in counting mode. The design and the performances of this detector in terms of yield, absolute efficiency, response and noise are reported. Spectra in the soft x-ray range of different elements (W, Ag, Al, Mg, Cu, N, C and B) obtained in WDS mode using this detector are presented. DUVEX appears as a competitive detection tool in terms of cost and easiness of implementation.