Search

Kidney transplantation is vital for treating end-stage renal disease, impacting roughly one in a thousand Europeans. The search for a suitable deceased donor often leads to prolonged and uncertain wait times, making living donor transplants a viable alternative. However, approximately 40% of living donors are incompatible with their intended recipients. Therefore, many countries have established kidney exchange programs, allowing patients with incompatible donors to participate in "swap" arrangements, exchanging donors with other patients in similar situations. Several variants of the vertex-disjoint cycle cover problem model the above problem, which deals with different aspects of kidney exchange as required. This paper discusses several specific vertex-disjoint cycle cover variants and deals with finding the exact solution. We employ the dataless neural networks framework to establish single differentiable functions for each variant. Recent research highlights the framework's effectiveness in representing several combinatorial optimization problems. Inspired by these findings, we propose customized dataless neural networks for vertex-disjoint cycle cover variants. We derive a differentiable function for each variant and prove that the function will attain its minimum value if an exact solution is found for the corresponding problem variant. We also provide proof of the correctness of our approach. [ABSTRACT FROM AUTHOR]

In this paper, we study Horn formulas from the perspective of read-once resolution refutations (RORs). A Horn formula is a Boolean formula in conjunctive normal form (CNF), in which each clause contains at most one positive literal. Horn formulas are used in a number of domains, including program verification, logic programming, and econometrics. In particular, deduction in ProLog is based on unification. Unification is based on resolution and instantiation. Resolution is a system used to prove the infeasibility of Boolean formulas. It is important to note that resolution is both sound and complete. However, resolution is inefficient in the following sense: There exist CNF formulas with resolution refutations whose lengths are bounded below by an exponential function of the input size. At the same time, these formulas admit shorter (polynomially bounded) proofs of infeasibility in other proof systems, such as Frege Systems. Despite this inefficiency, resolution is simple and easy to implement and hence used in a wide variety of theorem provers. In this paper, we study two variants of resolution. These are read-once resolution (ROR) and read-once unit resolution (UROR). Both ROR and UROR are sound. However, they are incomplete since there exist infeasible Boolean formulas which do not have either an ROR or a UROR. In this paper, we look at the problems of determining if a Horn formula has an ROR or a UROR. We also examine the problem of finding the optimal length ROR of a Horn formula from both the computational complexity and the approximation perspectives. Finally, we analyze the copy complexity of Horn formulas with respect to URORs. [ABSTRACT FROM AUTHOR]

Ultra-high molecular-weight polyethylene (UHMWPE) is one of the most extensively utilized supporting materials inside total knee replacement (TKR) because of its combination of outstanding mechanical qualities and wear resistance. The integrity of the hole is an essential component for fastening the femur and tibia elements in knee replacements. Due to its viscoelasticity behavior, it often causes difficulties such as rapid tool wear, burr formation, and poor finish in conventional machining operations, which causes poor hole features. Since unconventional methods are currently being investigated for drilling UHMWPE. Abrasive water jet drilling (AWJD) is particularly promising for handling hard-to-machine materials, and AWJ drilling of UHMWPE materials demands focus on it. The focus of this research is to determine the importance of AWJD variables for UHMWPE. In this experiment, 64 holes, each with a diameter of 10mm, were drilled into the sample material using a complete factorial approach to evaluation. Abrasive water jet pressure (AWJP) (210, 260, 310, and 360MPa), abrasive mass flow rate (AMFR) (250, 300, 350, and 400g/min.), and traverse rate (TR) (150, 300, 450, and 600mm/min.) were all taken into account. Furthermore, the geometrical properties of the hole, such as hole diameter (entry and exit), circularity, perpendicularity, and cylindricity, were investigated. The outcomes identified that both AWJP and TR played significant roles in determining the geometric features of the hole. During the drilling operation, the material removal mechanism and the hole defects were observed and identified using scanning electron microscopy (SEM). [ABSTRACT FROM AUTHOR]

In this paper, we analyze the copy complexity of unsatisfiable Horn constraint systems, under the ADD refutation system. Recall that a linear constraint of the form ∑ i = 1 n a i · x i ≥ b , is said to be a horn constraint if all the a i ∈ { 0 , 1 , - 1 } and at most one of the a i s is positive. A conjunction of such constraints is called a Horn constraint system (HCS). Horn constraints arise in a number of domains including, but not limited to, program verification, power systems, econometrics, and operations research. The ADD refutation system is both sound and complete. Additionally, it is the simplest and most natural refutation system for refuting the feasibility of a system of linear constraints. The copy complexity of an infeasible linear constraint system (not necessarily Horn) in a refutation system, is the minimum number of times each constraint needs to be replicated, in order to obtain a read-once refutation. We show that for an HCS with n variables and m constraints, the copy complexity is at most 2 n - 1 , in the ADD refutation system. Additionally, we analyze bounded-width HCSs from the perspective of copy complexity. Finally, we provide an empirical analysis of an integer programming formulation of the copy complexity problem in HCSs. (An extended abstract was published in FroCos 2021 [26].) [ABSTRACT FROM AUTHOR]

This paper is concerned with a new variant of bin packing called priority-based bin packing with subset constraints (PBBP-SC). PBBP-SC is a variant of traditional bin packing (TBP). In a TBP instance, we are given a collection of items { t 1 , t 2 , ... t n } , where each item t i has size s i ∈ (0 , 1). The goal of TBP is to pack the items in as few unit-sized bins as possible. In a PBBP-SC instance, we are given a collection of n unit-size items and a collection of m bins of varying capacities. Associated with each item is a positive integer which is called its priority. The priority of an item indicates its importance in being included in a (possibly infeasible) packing. As with the traditional case, these items need to be packed in the fewest number of bins. What complicates the problem is the fact that each item can be assigned to only one of a select set of bins, i.e., the bins are not interchangeable. We investigate several problems associated with PBBP-SC. The first problem we study is the feasibility problem. This is the problem of checking if there is a feasible assignment to a given PBBP-SC instance. The second problem we study is the priority maximization problem. This is the problem of finding a maximum priority assignment of an infeasible PBBP-SC instance. The third problem we study is the bin minimization problem. This is the problem of finding an assignment with the fewest number of bins to pack all of the items in a feasible PBBP-SC instance. We derive a number of results from both the algorithmic and computational complexity perspectives for these problems. In particular, we show that both the feasibility and priority maximization problems are solvable in polynomial time. We also show that the bin minimization problem is log-APX-complete and cannot be solved in time o (1. 4 1 m) unless the Strong Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

In this paper, we investigate refutability in Difference Constraint Systems (DCS) under the Unit Read-Once Refutation (UROR) system. A difference constraint is a linear relationship of the form: x i - x j ≤ b ij and a DCS is a conjunction of such constraints. In the UROR refutation system, each constraint can be used by at most one inference. Additionally, each inference has to use at least one one-variable (absolute) constraint. Note that an unsatisfiable difference constraint system may not have a UROR. Thus, the UROR refutation system is incomplete for DCSs. The UROR refutation system is useful for proving that the infeasibility of a DCS is caused by the current variable domains. These domains are determined by the absolute constraints in the system. Thus, the UROR refutations of a DCS depend on these variable domains. This is in contrast to unrestricted refutations which do not need to depend on these domain constraints. Investigating weak (incomplete) refutation systems leads to a better understanding of the inference rules required for establishing contradictions in the given constraint system. Thus, this study is well-motivated. Likewise, difference constraint systems arise in a number of application domains such as program verification and scheduling. It follows that efficient refutation systems are of paramount interest. In this paper, we show that problem of checking if a DCS has a unit read-once refutation is NP-complete. Additionally, we provide parameterized and exact exponential algorithms for solving this problem. Finally, we show that the problem of finding the length of the shortest unit read-once refutation is NPO PB-complete. [ABSTRACT FROM AUTHOR]

In this paper, we present two new graph structures that can be used to model information routing in heterogeneous communication networks. These are cardinality-constrained graphs (CCGs) and interval-constrained graphs (ICGs). In both cardinality- and interval-constrained graphs, the nodes in the graph are labeled. In a CCG, each label is associated with an upper bound. A path in a CCG is considered valid, if the number of nodes on the path with any particular label is at most the upper bound associated with that label. In an ICG, each label is associated with both an upper bound and a lower bound. A path in an ICG is considered valid, if the number of nodes on the path with any particular label is between the upper and lower bounds associated with that label. In this paper, we examine the computational complexities of finding valid paths in both CCGs and ICGs. In particular, we show that these problems are NP-hard. Additionally, we propose novel algorithms for finding paths in CCGs and a subset of ICGs. We also demonstrate the effectiveness of our algorithms on CCGs and ICGs of various sizes. The past decade has seen a surge in the degree of hardware-heterogeneous device interconnectivity, Additionally, there has been a proliferation of resource-constrained wireless sensor networks. Thus, the problems of finding valid paths in CCGs and ICGs are of interest. Nodes in wireless sensor networks can be faulty, vulnerable, energy-constrained, or untrusted. These nodes may also have differing degrees of performance or power efficiency. This can pose a significant challenge in routing the flow of information between nodes. The heterogeneity of nodes in such networks is captured through the use of CCGs and ICGs. [ABSTRACT FROM AUTHOR]

This paper is concerned with the design and analysis of a bit-scaling based algorithm for the problem of checking integer feasibility in a system of unit two variable per inequality (UTVPI) constraints (IF). The insights developed during algorithm design result in new techniques for extracting refutations of integer feasibility in such systems. Recall that a UTVPI constraint is a linear constraint of the form: a i · x i + a j · x j ≤ b ij , where a i , a j ∈ { 0 , 1 , - 1 } and b ij ∈ Z . These constraints arise in a number of application domains including but not limited to program verification (array bounds checking and abstract interpretation), operations research (packing and covering), and logic programming. Over the years, several algorithms have been proposed for the IF problem. Most of these algorithms are based on two inference rules, viz. the transitive rule and the tightening rule. None of these algorithms are bit-scaling. In other words, the running times of these algorithms are parameterized only by the number of variables and the number of constraints in the UTVPI constraint system (UCS) and not by the sizes of input constants. We introduce a novel algorithm for the IF problem, which is based on a collection of new insights. These insights are used to design a new bit-scaling algorithm for IF that runs in O (n · m · log 2 C) time, where n denotes the number of variables, m denotes the number of constraints, and C denotes the absolute value of the most negative constant defining the UCS. An interesting consequence of our research is the development of techniques for extracting refutations of integer infeasibility in UCSs that are linearly feasible. If the UCS is linearly feasible, then our algorithm creates a 2CNF formula. The UCS has an integer refutation (i.e., does not have a lattice point) if and only if the created 2CNF formula has a resolution refutation (i.e., is unsatisfiable). [ABSTRACT FROM AUTHOR]

In this paper, we investigate the properties of cutting plane based refutations for a class of integer programs called Horn constraint systems (HCSs). Briefly, a system of linear inequalities A ⋅x ≥b is called a Horn constraint system, if each entry in A belongs to the set {0,1,− 1} and furthermore, there is at most one positive entry per row. Our focus is on deriving refutations, i.e. proofs of unsatisfiability, of such programs using cutting planes as a proof system. We also look at several properties of these refutations. HCSs can be considered a more general form of Horn formulas, i.e., CNF formulas with at most one positive literal per clause. Cutting plane calculus (CP) is a well-known calculus for deciding the unsatisfiability of propositional CNF formulas and integer programs. Usually, CP consists of a pair of inference rules. These are called the addition rule (ADD) and the division rule (DIV). In this paper, we show that cutting plane calculus is still complete for HCSs when every intermediate constraint is required to be Horn. We also investigate the lengths of cutting plane proofs for Horn constraint systems. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the problems of finding minimum stopping sets and trapping sets in Tanner graphs, using integer linear programming. These problems are important for establishing reliable communication across noisy channels. Indeed, stopping sets and trapping sets correspond to combinatorial structures in information-theoretic codes, which lead to errors in decoding once a message is received. In particular, these sets correspond to variables that are not eventually corrected by the decoder, thus causing failures in decoding when using iterative algorithms. We present integer linear programs (ILPs) for finding stopping sets and several trapping set variants. Furthermore, we prove that two of these trapping set problem variants are NP-hard for the first time. Additionally, we analyze these variants from the parameterized perspective. Finally, we model stopping set and trapping set problems as Integer Linear Programs (ILPs). The effectiveness of our approach is demonstrated by finding stopping sets of size up to 48 in the (4896 , 2474) Margulis code. This compares favorably to the current state-of-the-art, which finds stopping sets of size up to 26. For the trapping set problems, we show for which cases an ILP produces solutions efficiently and for which cases it performs poorly. The proposed approach is applicable to codes represented by regular and irregular graphs alike.1 [ABSTRACT FROM AUTHOR]

In this paper, we discuss algorithms for the problem of finding read-once resolution refutations of unsatisfiable 2CNF formulas within the resolution refutation system. Broadly, a read-once resolution refutation is one in which each constraint (input or derived) is used at most once. Read-once resolution refutations have been widely studied in the literature for a number of constraint system-refutation system pairs. For instance, read-once resolution has been analyzed for boolean formulas in conjunctive normal form (CNF) and read-once cutting planes have been analyzed for polyhedral systems. By definition, read-once refutations are compact, and hence valuable in applications that place a premium on visualization. The satisfiability problem (SAT) is concerned with finding a satisfying assignment for a boolean formula in CNF. While SAT is NP-complete in general, there exist some interesting subclasses of CNF formulas, for which it is decidable in polynomial time. One such subclass is the class of 2CNF formulas, i.e., CNF formulas in which each clause has at most two literals. The existence of efficient algorithms for satisfiability checking in 2CNF formulas (2SAT), makes this class useful from the perspective of modeling selected logic programs. The work in this paper is concerned with the read-once refutability problem (under resolution) in this subclass. Although 2SAT is decidable in polynomial time, the problem of finding a read-once resolution refutation of an unsatisfiable 2CNF formula is NP-complete. We design non-trivial, parameterized and exact exponential algorithms for this problem. Additionally, we study the computational complexity of finding a shortest read-once resolution refutation of a 2CNF formula. [ABSTRACT FROM AUTHOR]

In this paper, we propose several algorithms for determining an optimal length tree-like refutation of linear feasibility in systems of Unit Two Variable Per Inequality (UTVPI) constraints. Given an infeasible UTVPI constraint system (UCS), a refutation certifies its infeasibility. The problem of finding refutations in a UCS finds applications in domains such as program verification and operations research. In general, there exist several types of refutations of feasibility in constraint systems. In this paper, we focus on a specific type of refutation called a tree-like refutation. Tree-like refutations are complete , in the sense that if a system of linear constraints is infeasible, then it must have a tree-like refutation. Associated with a refutation is its length, which equals the total number of constraints (accounting for the reuse of constraints) that are used to establish the infeasibility of the corresponding linear constraint system. Our goal in this paper is to find an optimal length tree-like refutation (OTLR) of an infeasible UCS. We describe two deterministic algorithms that find an OTLR of a UCS. If m is the number of constraints, n is the number of variables in the system, and k is the length of an OTLR, then our two algorithms run in O (n 3 ⋅ log k) time and O (m ⋅ n ⋅ k) time respectively. We also propose a true-biased, randomized algorithm for this problem. This algorithm runs in O (m ⋅ n ⋅ log n) time, and returns the length of an OTLR with probability (1 − 1 e). We extend our work to weighted UTVPI constraint systems (WUCS), where a positive weight is associated with each UTVPI constraint. The weight of a tree-like refutation is defined as the sum of the weights of the constraints used by the refutation. The problem of finding a minimum weight refutation in a WUCS is called the weighted optimal length tree-like refutation (WOTLR) problem and is known to be NP-hard. We propose a pseudo-polynomial time algorithm for the WOTLR problem and convert it into a fully polynomial time approximation scheme (FPTAS). [ABSTRACT FROM AUTHOR]

[Display omitted] The supercapattery, an ideal electrochemical energy storage device, which can deliver high energy like battery and high power like supercapacitor. Transition metal sulphides' energy storage capabilities have unfurled beyond the realm of ruthenium and manganese-based oxides by the versatile affordable sulphospinel transition metal sulphides such as MnCo 2 S 4 (MCS). The advancement of synergistic nano-architectures of these transition metal sulphides with two-dimensional MXene material adulated the conductivity and highly reversible redox nature. The hybrid MCS-MXene was synthesised through facile cost effective hydrothermal method and the material were characterised using basic X-Ray Diffraction (XRD) to advanced tools as like electron energy loss spectroscopy (EELS). The electrochemical results depict that the supercapattery electrode of 2D synergistic MCS-MXene hybrid architectures shows highly improved specific capacitance of 600 C/g at 1 A/g current density than pristine MXene and MCS. The fabricated asymmetric supercapattery using hybrid MCS-MXene and bio-derived activated carbon (AC) shows a high specific energy and power density of 25.6 Wh/kg and 6400 W/kg, respectively with excellent cycling stability of 100% capacitance retention after 12,000 cycles. [ABSTRACT FROM AUTHOR]

• The copy complexity of a Horn formula equals the copy complexity of the corresponding system of constraints. • The copy complexity of Horn formulas with respect to unit resolution is (m − 1) when copies of derived clauses are allowed. • A polynomial time algorithm that can determine if a 2-CNF formula has a unit read-once resolution refutation. In this paper, we discuss the copy complexity of Horn formulas with respect to unit resolution. A Horn formula is a boolean formula in conjunctive normal form (CNF) with at most one positive literal per clause. Horn formulas find applications in a number of domains, such as program verification (abstract interpretation) and logic programming (answer set programming). Quantified Horn clauses are used extensively in temporal verification of universal properties. Resolution is one of the oldest proof systems (refutation systems) for the boolean satisfiability problem (SAT), when the input is presented in conjunctive normal form (CNF). It is both sound and complete, although inefficient, when compared to other stronger proof systems for boolean formulas. Despite its inefficiency, the simple nature of resolution makes it an integral part of several theorem provers. Unit resolution is a restricted form of resolution in which each resolution step needs to use a clause with only one literal (unit literal clause). While not complete for general CNF formulas, unit resolution is complete for Horn formulas. Read-once resolution is a form of resolution in which each clause (input or derived) may be used in at most one resolution step. As with unit resolution, read-once resolution is incomplete in general and complete for Horn clauses. This paper focuses on a combination of unit resolution and read-once resolution called unit read-once resolution. Unit read-once resolution is incomplete for Horn clauses. In this paper, we study the copy complexity problem in Horn formulas with respect to unit read-once resolution. Briefly, the copy complexity of a formula with respect to unit read-once resolution, is the smallest number k , such that replicating each clause k times guarantees the existence of a unit read-once resolution refutation (UROR). This paper focuses on two problems related to the copy complexity of Horn formulas with respect to unit read-once resolution. We first relate the copy complexity of Horn formulas with respect to unit read-once resolution to the copy complexity of the corresponding Horn constraint system with respect to the addition rule. We also examine a form of copy complexity in which we permit replication of derived clauses, in addition to the input clauses. Finally, we provide a polynomial time algorithm for the problem of checking if a 2-CNF formula has a UROR. [ABSTRACT FROM AUTHOR]

Doped NiMn 2 O 4 /rGO nanocomposite shows very high specific capacitance of 710 F/g at 1 A/g. Fabricated aqueous symmetric supercapacitor exhibits excellent energy density and power density of 43 Wh/kg and 10 kW/kg, respectively with 90% of capacitance retention over 10,000 cycles. [Display omitted] • Specific capacitance of NiMn 2 O 4 increased from 254 to 710 F/g by doping. • High energy (43 Wh/kg) and power density (10 kW/kg) was achieved for NCZMOR-II. • High capacitanceretention of 90% over 10,000 cycles attained for NCZMOR-II. The transition metal ions (TMIs) such as Co2+ and Zn2+ doped NiMn 2 O 4 (NMO)/rGO nanocomposite synthesized by facile sol-gel method was used for the fabrication of supercapacitor. The presence of metal ions in the nanocomposite was confirmed by X-ray photoelectron spectroscopy (XPS) and high resolution transmission electron microscope (HR-TEM) mapping techniques. The fabricated electrode showed high specific capacitance of 710 F/g which was 3-fold higher than NMO (254 F/g). The addition of RGO in the nanocomposite increased the cycle stability of TMIs doped NMO significantly from 51 to 91%. In addition, the symmetric supercapacitor (SSC) fabricated using TMIs doped NMO/rGO nanocomposite with 3.5 M KOH as an electrolyte delivered a maximum energy density of 43 Wh/kg and power density of 10 kW/kg. Furthermore, the SSC device retained 90% of capacitance retention over 10,000 cycles with coulombic efficiency of 99% at 5 A/g. These result suggested that the TMIs doped NMO/rGO nanocomposite electrode is a promising material for high-energy supercapacitors. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of finding read-once refutations (ROR) of linear feasibility in a specialized class of constraint systems called UTVPI+ constraint systems (UCS +). The refutations in this paper are analyzed using the ADD inference rule. Recall that a Unit Two Variable Per Inequality (UTVPI) constraint is a constraint of the form a i ⋅ x i + a j ⋅ x j ≤ b , where b ∈ Z , and a i , a j ∈ { 0 , 1 , − 1 }. A conjunction of such constraints is called a UTVPI constraint system (UCS). UCSs find applications in a number of domains such as abstract interpretation and scheduling. We examine a more general form of UCSs that allows for a limited number of non-UTVPI constraints to be added to a UCS. We refer to these more general UCSs as UTVPI+ constraint systems or UCS + s. If a UCS + has only k non-UTVPI constraints, then we refer to it as a UCS k +. Our focus in this paper is on refutations, i.e., proofs of infeasibility in UCS + s. In particular, we study read-once refutations of linear feasibility in UCS + s. Although the problem of finding read-once refutations of UCSs is polynomial time solvable, the presence of non-UTVPI constraints makes the problem NP-hard. However, if the number of non-UTVPI constraints is fixed, then read-once refutations can be found in polynomial time. In fact, in this paper, we show that the ROR problem is fixed-parameter tractable (FPT) for UCS k + s , with respect to k , the number of non-UTVPI constraints in the system. We also provide a lower bound on the efficiency of a class of parameterized algorithms for this problem, based on the Strong Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]

The HASC cell delivered 89% of the initial specific capacity after 1,00,000 charge–discharge cycles (coulombic efficiency of the cell is 99.6%). Ragone plot for the S-gC 3 N 4 /CoS 2 -II nanocomposite based fabricated hybrid asymmetric cell exhibited a high energy density of 32 Wh/kg and power density of 800 W/kg at 1 A/g current density. • HSAC was fabricated with S-gC 3 N 4 /CoS 2 nanocomposite and bio-derived carbon. • A high specific capacity of 180 C/g at 1 A/g current density was achieved. • A high energy 32 Wh/kg, power density 19.8 kW/kg was delivered in aqueous electrolyte. • High stability 100,000 cycles (89%) at 30 A/g with coulombic efficiency of 99.6%. This work demonstrates a high-performance hybrid asymmetric supercapacitor (HASC) workable in very high current density of 30 A g−1 with in-situ pyrolytic processed sulfur-doped graphitic carbon nitride/cobalt disulfide (S-gC 3 N 4 /CoS 2) materials and bio-derived carbon configuration and achievement of high electrochemical stability of 89% over 100,000 cycles with the coulombic efficiency of 99.6%. In the electrochemical studies, the S-gC 3 N 4 /CoS 2 -II electrode showed a high specific capacity of 180 C g−1 at 1 A g−1 current density in the half-cell configuration. The HASC cell was fabricated using S-gC 3 N 4 /CoS 2 -II material and orange peel derived activated carbon as a positive and negative electrode with a maximum operating cell potential of 1.6 V, respectively. The fabricated HASC delivered a high energy density of 26.7 Wh kg−1 and power density of 19.8 kW kg−1 in aqueous electrolyte. The prominent properties in specific capacity and cycling stability could be attributed to the CoS 2 nanoparticles engulfed into the S-gC 3 N 4 framework which provides short transport distance of the ions, strong interfacial interaction, and improving structural stability of the S-gC 3 N 4 /CoS 2 -II materials. [ABSTRACT FROM AUTHOR]

As the modern integrated circuit continues to grow in complexity, the design of very large-scale integrated (VLSI) circuits involves massive teams employing state-of-the-art computer-aided design (CAD) tools. An old yet significant CAD problem for VLSI circuits is physical design automation. In physical design automation, we need to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface. The process of mapping an electronic design to a chip involves several physical design stages, one of which is clustering. Even for combinatorial circuits, there are several models for the clustering problem. In particular, we consider the problem of clustering without replication in combinatorial circuits with a view towards minimizing delay (CN). The corresponding problem with replication has been well-studied and solvable in polynomial time. However, replication can become expensive when it is unbounded. Consequently, CN is a problem worth investigating. We establish the computational complexities of several variants of CN. Additionally, we obtain approximability and inapproximability results for some NP-hard variants of CN. We also present approximation and exact exponential algorithms for some variants of CN. We prove that for some cases there exists an approximation factor of strictly less than two and that our exact exponential algorithms beat brute force. Furthermore, we provide the first parameterized approximation algorithm in which the approximation ratio is also a parameter. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of computing the lattice point closure of a conjunction of Unit Two Variable Per Inequality (UTVPI) constraints. We accomplish this by adapting Johnson's all pairs shortest path algorithm to UTVPI constraint systems (UCSs). Thus, we obtain a closure algorithm that is efficient for sparse constraint systems. This problem has been extremely well-studied in the literature, since it arises in a number of applications, including but not limited to, program verification and operations research. In UTVPI constraints, linear feasibility does not always imply integer feasibility. Thus, there is a difference between the linear closure of a UCS and the integer closure of that same system. Finding the linear closure requires only a single inference rule called the transitive inference rule. This inference rule corresponds to the addition of constraints and preserves both linear and integer solutions. The problem of finding the integer closure requires the use of the tightening inference rule. Unlike the transitive inference rule, the tightening inference rule does not preserve linear solutions. However, it does preserve integer solutions. The complexity of solving the integer closure problem has steadily improved over the past several decades with the fastest algorithm for this problem running in time O(n3) on a UCS with n variables and m constraints. For the same input parameters, we detail an algorithm that runs in time O (m ⋅ n + n 2 ⋅ log n) . It is clear that our algorithm is superior to the state of the art when the UCS is sparse (m ∈ o(n2)), and no worse than the state of the art when the UCS is dense (m ∈Θ(n2)). The best known running time for computing the closure of a conjunction of difference constraints (m constraints, n variables) is O (m ⋅ n + n 2 ⋅ log n) , and UTVPI constraints subsume difference constraints. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the design and analysis of polynomial time algorithms for two problems associated with a linearly infeasible system of Unit Two Variable Per Inequality (UTVPI) constraints, viz., (a) the read-once refutation (ROR) problem, and (b) the literal-once refutation (LOR) problem. Recall that a UTVPI constraint is a linear relationship of the form: a i · x i + a j · x j ≤ b ij , where a i , a j ∈ { 0 , 1 , - 1 } . A conjunction of such constraints is called a UTVPI constraint system (UCS) and can be represented in matrix form as: A · x ≤ b . These constraints find applications in a host of domains including but not limited to operations research and program verification. For the linear system A · x ≤ b , a refutation is a collection of m variables y = [ y 1 , y 2 , ... , y m ] T ∈ R + m , such that y · A = 0 , y · b < 0 . Such a refutation is guaranteed to exist for any infeasible linear program, as per Farkas' lemma. The refutation is said to be read-once, if each y i ∈ { 0 , 1 } . Read-once refutations are incomplete in that their existence is not guaranteed for infeasible linear programs, in general. Indeed they are not complete, even for UCSs. Hence, the question of whether an arbitrary UCS has an ROR is both interesting and non-trivial. In this paper, we reduce this problem to the problem of computing a minimum weight perfect matching (MWPM) in an undirected graph. This transformation results in an algorithm that runs in in time polynomial in the size of the input UCS. Additionally, we design a polynomial time algorithm (also via a reduction to the MWPM problem) for a variant of read-once resolution called literal-once resolution. The advantage of reducing our problems to the MWPM problem is that we can leverage recent advances in algorithm design for the MWPM problem towards solving the ROR and LOR problems in UCSs. Finally, we show that another variant of read-once refutation problem called the non-literal read-once refutation (NLROR) problem is NP-complete in UCSs. [ABSTRACT FROM AUTHOR]

With high power density and promising possibilities for high energy density, the electrochemical capacitor has become an indispensable energy storage device to satisfy the future energy demands. Here in, we report on synthesis of graphene nanosheets (GNS) supported manganese sulfide (MnS) hybrid (GNS-MnS) nanocomposite by a simple, facile hydrothermal process. The resultant GNS-MnS hybrid nanocomposite with robust electronic amalgamation facilitates swift transfer of both ions and electrons across the interface between electrode surface and electrolyte ions than pristine MnS. Benefiting from the better conduction along with improved active sites of the MnS in GNS-MnS hybrid nanocomposite, a high ratio surface/near-surface reactions is dominated by high specific capacity even at high current rate. As such, the GNS-MnS hybrid nanocomposite exhibited a maximum specific capacitance of 792 F g−1 at 2 A g−1 along with better retention rate of 58% at 15 A g−1, is significantly higher than that of pristine MnS (423 F g−1 at 2 A g−1 and 37% retention at 15 A g−1). In addition, the fabricated symmetric GNS-MnS hybrid nanocomposite cell delivered a high energy density of 25 W h kg−1 and power density of 7160 W kg−1. Moreover, specific capacitance of 91.1% is retained after 15000th cycles with columbic efficiency of ∼100% at 20 A g−1. The remarkable electrochemical performance of GNS-MnS hybrid nanocomposite electrode demonstrated its potential as a key material for developing high energy supercapacitors. Image 1 • Facile synthesis of graphene nanosheets - manganese sulfide (GNS – MnS) hybrid nanocomposite by a simple hydrothermal method. • GNS - MnS hybrid nanocomposite exhibited a maximum specific capacitance of 792 F g−1 at 2 A g−1 than the pristine MnS. • GNS-MnS hybrid nanocomposite symmetric cell delivered a high energy density of 25 W h kg−1and power density of 7.16 kW kg−1. • The symmetric cell showed ∼91% electrochemical stability for 15,000 cycles. [ABSTRACT FROM AUTHOR]

Graphical abstract Highlights • Hexagonal ZnO nanoflowers/reduced graphene oxide nanocomposite preparation via simple chemical decomposition method. • The synthesized nanocomposite exhibited a high specific capacitance of 203 F g−1. • The nanocomposite showed ∼98% electrochemical stability for 10,000 cycles. Abstract We demonstrated a facile and scalable synthesis of crystalline hexagonal ZnO nanoflowers/reduced graphene oxide nanocomposite (ZnO-NFs/RGO NCs) via direct chemical decomposition of zinc hexacyanoferrate (ZnHCF) over reduced graphene oxide (RGO) nanosheets. The phase formation and degree of functionalization of as-synthesized ZnO-NFs/RGO NCs was confirmed from XRD and FT-IR spectroscopic analysis, respectively. The hierarchical ZnO nanoflowers consist of 2D nanosheets wrapped with RGO nanosheets was confirmed from FE-SEM and HR-TEM images. The synthesized ZnO-NFs/RGO NCs exhibits a high specific capacitance of 203 F g−1 at the current density of 1 A g−1 with good rate performance and also showed an excellent electrochemical stability of 98% for 10,000 cycles at high current density of 20 A g−1. [ABSTRACT FROM AUTHOR]

In this paper, we study the efficacy of several mathematical programming formulations for the single-source shortest path problem, the negative cost cycle detection problem, and the shortest negative cost cycle problem in arc-dependent networks. In an arc-dependent network, the cost of an arc a depends upon the arc preceding a. These networks differ from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. Arc-dependent networks are useful for modeling a number of real-world problems, such as the turn-penalty shortest path problem, which cannot be captured in the traditional network setting. We present new integer and non-linear programming formulations for each problem. We also perform the first known empirical study for arc-dependent networks to contrast the execution times of the two formulations on a set of graphs with varying families and sizes. Our experiments indicate that although non-linear programming formulations are more compact, integer programming formulations are more efficient for the problems studied in this paper. Additionally, we introduce a number of cuts for each integer programming formulation and examine their effectiveness. [ABSTRACT FROM AUTHOR]

This paper is concerned with designing algorithms for and analyzing the computational complexity of the partial vertex cover problem in trees. Graphs (and trees) are frequently used to model risk management in various systems. In particular, Caskurlu et al. in [4] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. In this paper, we focus on a special case of the partial vertex cover problem, when the input graph is a tree. We consider four possible versions of this setting, depending on whether or not, the vertices and edges are weighted. Two of these versions, where edges are assumed to be unweighted, are known to be polynomial-time solvable. However, the computational complexity of this problem with weighted edges, and possibly with weighted vertices, remained open. The main contribution of this paper is to resolve these questions by fully characterizing which variants of partial vertex cover remain NP-hard in trees, and which can be solved in polynomial time. In the paper, we propose two pseudo-polynomial DP-based algorithms for the most general case in which weights are present on both the edges and the vertices of the tree. One of these algorithms leads to a polynomial-time procedure, when weights are confined to the edges of the tree. The insights used in this algorithm are combined with additional scaling ideas to derive an FPTAS for the general case. A secondary contribution of this work is to propose a novel way of using centroid decompositions in trees, which could be useful in other settings as well. [ABSTRACT FROM AUTHOR]

Abstract: Nickel telluride nanorods (NiTe NRs) have been prepared by hydrothermal method using ascorbic acid as reducing agent and CTAB as surfactant and characterized by XRD, FE‐SEM, HR‐TEM and BET. EDX analysis confirms the formation of NiTe NRs. NiTe electrode material for supercapacitor is characterized by cyclic voltammetry (CV), galvanostatic charge‐discharge (GCD) and electrochemical impedance spectroscopy (EIS) measurements. A high specific capacitance of 618 F g−1 at the current density of 1 A g−1 and the cyclic stability with 75% of its specific capacitance retention after 5000 cycles are achieved. During the cyclic process, the coulombic efficiency is better than 99% indicating a good reversibility of NiTe electrode. The combination of high electrical conductivity, porous structure and the synergic effects of nickel play a significant role to obtain supercapacitor electrodes with excellent performances. [ABSTRACT FROM AUTHOR]

In this paper, we design and analyze a fast, randomized algorithm for the problem of finding a negative cost cycle having the smallest number of edges in a directed, weighted graph. This problem will henceforth be referred to as the Shortest Negative Cost Cycle problem (SNCC). SNCC is closely related to the problem of checking whether a directed, weighted graph contains a negative cost cycle (NCCD). NCCD is an extremely well-studied problem within the domains of operations research and theoretical computer science. SNCC is important in its own right and finds several applications in program verification (Satisfiability modulo theories), abstract interpretation and real-time scheduling. It is also an important subroutine in solving the generalized submodular flow problem, which has applications in trading networks. The randomized algorithm presented in this paper for SNCC determines a shortest negative cost cycle with probability at least ( 1 − e − 1 ) in O ( m ⋅ n ⋅ log n ) time, on a network with n vertices and m edges. This is, in general, a significant improvement over the best deterministic bound of O ( m ⋅ n ⋅ | C ∗ | ) over the same parameters, where C ∗ is a shortest negative cost cycle. This algorithm requires Ω ( n ⋅ log n ) random bits. We then propose a second randomized algorithm that runs in O ( m ⋅ n ⋅ log n ) expected time and requires O ( n ) random bits (expected). [ABSTRACT FROM AUTHOR]

We report on a simple and facile synthesis of manganese ferrite (MnFe 2 O 4 ) nanoparticles by chemical co-precipitation method using 1 M NaOH as the oxidative solution. The resultant nanoparticles were characterized by using various tools like powder X-ray diffraction, Fourier transform infrared spectroscopy and scanning electron microscopy. The morphology of the resultant product was observed to be of spherical in shape with diameter of about 20–50 nm. The electrochemical performance of manganese ferrite nanoparticles was investigated by using cyclic voltammetry, charge–discharge and electrochemical impedance spectroscopy with different electrolytes, such as 1 M LiNO 3 , 1 M Li 3 PO 4 and KOH. In a three-electrode system, a maximum specific capacitance of 173, 31 and 430 F g −1 was attained corresponding to the electrolytes of 3.5 M KOH, 1 M LiNO 3 and 1 M Li 3 PO 4 , respectively. Among these, 3.5 M KOH electrolyte medium exhibited excellent rate performance, evidently more than 60% of retention was observed at 10 A g −1 due to the synergistic activities, high surface accessibility and better electronic conductivity of MnFe 2 O 4 nanoparticles. In addition, the fabrication of symmetric cell using MnFe 2 O 4 as an electrode materials with 3.5 M KOH as an electrolyte, exhibited maximum specific capacitance, high energy density and power density of 245 F g −1 , 12.6 Wh kg −1 and 1207 W kg −1 , respectively. Furthermore, the specific capacitance of 105% retained after 10,000 cycles at the high current density of 1.5 A g −1 and the coulombic efficiency of the all 10,000 cycles remains constant (∼98) which clearly displayed the excellent electrochemical stability of MnFe 2 O 4 nanosphere (NS). Our results may pave the way for employing the low-cost co-precipitation method to fabricate advanced high energy storage and highly stable device with long cycle life. [ABSTRACT FROM AUTHOR]

In this paper, we examine variants of the partial vertex cover problem from the perspective of parameterized algorithms. Recall that in the classical vertex cover problem (VC), we are given a graph G = ⟨ V , E ⟩ and a number k and asked if we can cover all of the edges in E , using at most k vertices from V . The partial vertex cover problem (PVC) is a more general version of the VC problem in which we are given an additional parameter k ′ . We then ask the question of whether at least k ′ of the edges in E can be covered using at most k vertices from V . Note that the VC problem is a special case of the PVC problem when k ′ = | E | . In this paper, we study the weighted generalizations of the PVC problem. This is called the weighted partial vertex cover problem (WPVC). In the WPVC problem, we are given two parameters R and L, associated respectively with the vertex set V and edge set E of the graph G respectively. Additionally, we are given non-negative integral weight functions for the vertices and the edges. The goal then is to cover edges of total weight at least L, using vertices of total weight at most R. This paper studies several variants of the PVC and WPVC problems and establishes new results from the perspective of fixed-parameter tractability and W[1]-hardness. We also introduce a new problem called the partial vertex cover with matching constraints and show that it is Fixed-Parameter Tractable (FPT) for a certain class of graphs. Finally, we show that the WPVC problem is APX-complete for bipartite graphs. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a new combinatorial certifying algorithm for the problem of checking linear feasibility in Unit Two Variable Per Inequality (UTVPI) constraints. A UTVPI constraint has at most two non-zero variables and the coefficients of the non-zero variables belong to the set $$\{+1,\ -1\}$$ . These constraints occur in a number of application domains, including but not limited to program verification, abstract interpretation, and operations research. The proposed algorithm runs in $$O(m\cdot n)$$ time and $$O(m+n)$$ space on a UTVPI system with n variables and m constraints. Observe that these resource bounds match the bounds of the fastest strongly polynomial algorithm for difference constraints. Inasmuch as UTVPI constraints subsume difference constraints, it is clear that the resource requirements of our algorithm are optimal. Additionally, our algorithm is certifying, in that it produces a satisfying assignment when presented with a feasible instance, and a refutation, otherwise. At the heart of our algorithm is a new constraint network representation for UTVPI constraints. [ABSTRACT FROM AUTHOR]

Doped carbon allotropes are promising materials for use in a range of applications in energy harvesting and gas adsorption. Synthesis of multifunctional C is however challenging as it requires simultaneous control over surface area, conductivity, chemical nature and loading of heteroatoms in the carbon matrix, usually yielding a material at a time that favours a single application. Pyridinic-N on C-surface, for instance, facilitates oxygen reduction (ORR) and CO 2 capture, whereas more heteroatom enhances capacitance. Here we report on soya derived N-doped carbon having high surface area of 1072 m 2 /g and exhibiting superior performance for all these applications. Supercapacitors made of this material is operable in a wide potential window and possesses specific energy density of 24.3 Wh/kg with 93% capacitive retention beyond 10,000 charge-discharge cycles at a high 10 A/g discharge rate. It also exhibits one of the best performances among bio-derived materials towards ORR with half wave potential of −0.211 V ( vs . SCE) in alkaline solution that involve facile multi-electron transfer at rate determining step. Further at 1 bar pressure, it captures an appreciable 14 wt% CO 2 at 25 °C and 57.7 wt% at −78 °C. [ABSTRACT FROM AUTHOR]

Corncob carbon prepared by means of (KOH) chemical activation method at 600 °C for 1 h is shown as a promising electrode material for supercapacitors. The XRD analysis of the activated corncob carbon shows highly amorphous and disordered structure. The specific surface area and pore volume of the activated carbon are analysed using Brunauer-Emmett-Teller (BET) method. The calculated BET surface area of activated corncob carbon is ∼ 800 m 2 g −1 with micro and mesoporous in nature. The porous nature of the carbon is further confirmed using SEM and HR-TEM analysis. The electrochemical studies in aqueous electrolytes reveal that a high specific capacitance of 390 F g −1 at 0.5 A g −1 current density. The electrochemical performance of activated corncob electrodes is studied in three different ionic liquids, among them the EMIMBF 4 possess good capacitive behaviour and the wide potential window resulted a high energy density of 25 Wh kg −1 and power density of 174 W kg −1 . The supercapacitor device fabricated using the ionic liquid could power a red LED for more than 4 min after upon 10 s charging. The above investigation clearly indicates that the corncob derived carbon materials are promising for applications in supercapacitor. [ABSTRACT FROM AUTHOR]

In this paper, we detail a new algorithm for the problem of checking linear and integer feasibility in a system of Horn constraints. For certain special cases, the proposed algorithm is faster than the “Lifting Algorithm” for Horn constraint feasibility described in [2] . Moreover, the new approach is based on different ideas and in fact exploits several properties of Horn constraint systems (HCS) which were heretofore unknown, to the best of our knowledge. In the case of constraints of bounded width (corresponding to “loosely coupled” systems), our algorithm can be modified to run in O ( n 3 + m ⋅ n + m ⋅ n 2 log ⁡ ( max ⁡ ( m , n ) ) ) time, where n and m represent the number of variables and the number of constraints respectively, in the input HCS. Our main result establishes that checking the feasibility of an HCS can be reduced to three subproblems: negative-cost cycle detection in networks (NCCD), matrix–vector multiplication (MV), and the conversion of an HCS to a non-redundant set of difference constraints (H2D). The MV problem and the NCCD problem have both been studied extensively, as per the literature and there exist specialized, fast algorithms for the cases that are relevant to feasibility checking in Horn constraint systems. We have identified a new problem, viz., H2D, which warrants future research, since improved algorithms for the H2D problem could be implemented in our algorithm to decrease its running time even further. [ABSTRACT FROM AUTHOR]

This paper discusses the implementation of a new parallel algorithm for the negative cost girth (NCG) problem. The girth of an unweighted graph (directed or undirected) is defined as the length of the shortest cycle in the graph. We extend the notion of girth to networks with arbitrary weights in the following way: The negative cost girth of a network is the number of edges of the shortest negative cost cycle (i.e., the negative cost cycle with the fewest number of edges). The NCG problem has been well-studied, and there exist several polynomial time algorithms for the same. This problem finds applications in several domains, including constraint-solving, real-time scheduling, and program verification. In this paper, our focus is on a parallel implementation for solving the NCG problem that runs in $$O(\log k \cdot \log n)$$ parallel time using $$O(n^3)$$ processors, where $$n$$ is the number of vertices, and $$k$$ is the NCG. We conduct an empirical analysis for both the parallel implementation, using MPI, and the corresponding sequential NCG implementation. Our experiments indicate that as the number of processors doubles, the total execution time reduces by approximately one-half. [ABSTRACT FROM AUTHOR]

In this paper, we discuss certifying algorithms for zero-clairvoyant scheduling (ZCS) problems. ZCS problems are a class of real-time scheduling problems defined in the E-T-C scheduling framework [Subramani, K. (2005) A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. Comput. J., 48, 259–272]. In ZCS, the dispatcher has no knowledge of the execution time of a given job, even after the job has finished executing. A polynomial-time algorithm for ZCS was proposed in previous work of the first author [Subramani, K. (2007) A polynomial time algorithm for zero-clairvoyant scheduling. J. Appl. Logic, 5, 667–680]. However, the algorithm proposed therein is not certifying. The algorithm that we propose in this paper is certifying, in that it provides a structure that certifies the ‘yes’-instances and another structure that certifies the ‘no’-instances of ZCS problems. These structures make the discovery of implementation errors straightforward and greatly simplify the software development cycle. Moreover, the certifying algorithm has the same running time (asymptotically) as its non-certifying counterpart. We also show that the proposed certifying technique can be used to certify a class of mathematical programs called E-Quantified Polyhedral programs (E-QPPs). However, for E-QPPs, the proposed certifying algorithm has a higher asymptotic running time than its non-certifying counterpart. [ABSTRACT FROM AUTHOR]

Abstract: Single crystals of Dimethylaminomethylphthalimide cadmium chloride (DAMPCC) were grown by a slow evaporation technique. The unit cell parameters and crystal structure were measured by the powder X-ray diffraction analysis. The modes of vibrations of different molecular groups present in the DAMPCC crystal have been identified by FTIR spectral analysis. The UV–vis–NIR spectral analysis is used to study the optical behaviors like absorption and transmission properties of the crystal. The diffuse reflectance spectrum in absorption studies is calculated. The optical band gap of the DAMPCC crystal is calculated to be cut off wavelength 360nm at photon energy 4.772eV. The optical conductivity, electrical conductivity and ac conductivity are also calculated. Finally the nonlinear optics (NLO) property of DAMPCC crystal was confirmed by second harmonic generation (SHG) test using the Nd:YAG laser of fundamental wavelength 1064nm. [Copyright &y& Elsevier]

This paper is concerned with the design and analysis of improved algorithms for determining the optimal length resolution refutation (OLRR) of a system of difference constraints over an integral domain. The problem of finding short explanations for unsatisfiable Difference Constraint Systems (DCS) finds applications in a number of design domains including program verification, proof theory, real-time scheduling, and operations research. These explanations have also been called 'certificates' and 'refutations' in the literature. This problem was first studied in Subramani (J Autom Reason 43(2):121-137, ), wherein the first polynomial time algorithm was proposed. In this paper, we propose two new strongly polynomial algorithms which improve on the existing time bound. Our first algorithm, which we call the edge progression approach, runs in O( n · k + m · n · k) time, while our second algorithm, which we call the edge relaxation approach, runs in O( m · n · k) time, where m is the number of constraints in the DCS, n is the number of program variables, and k denotes the length of the shortest refutation. We conducted an extensive empirical analysis of the three OLRR algorithms discussed in this paper. Our experiments indicate that in the case of sparse graphs, the new algorithms discussed in this paper are superior to the algorithm in Subramani (J Autom Reason 43(2):121-137, ). Likewise, in the case of dense graphs, the approach in Subramani (J Autom Reason 43(2):121-137, ) is superior to the algorithms described in this paper. One surprising observation is the superiority of the edge relaxation algorithm over the edge progression algorithm in all cases, although both algorithms have the same asymptotic time complexity. [ABSTRACT FROM AUTHOR]

A micellar catalyzed oxidation of pentaamminecobalt(III) complexes of α-amino acids by Mn(III)acetate in acidic medium yielding nearly 100% Co(II) and about 100% carbonyl compounds are ultimate products. The unbound amino acids yield about 100% of carbonyl compound in presence of micelles. The effect of variation of sulphuric acid has been carried. The decrease in UV-Visible absorbance at λ=502 nm for Co(III) complex corresponds to nearly 100% of the initial absorbance. In spite of the stoichiometry of Mn(III) to unbound ligand is 2:1, the ratio of Mn(III) to cobalt(III) complex is 1:1 accounting for about 100% reduction at the cobalt(III) centre. The kinetic and stoichiometric results have been accounted. A suitable mechanism consistent with the experimental findings has been proposed by involving a radical cation intermediate. [ABSTRACT FROM AUTHOR]

Objectives: (i) To evaluate biodegradation, hard and soft tissue integration using various polyethylene glycol (PEG) hydrogels; (ii) to evaluate the influence of arginine-glycine-aspartic acid (RGD) on two types of PEG hydrogels. Material and methods: In seven rabbits, six treatment modalities were randomly applied subperiosteally on the skull: (1) a dense network PEG hydrogel (PEG1), (2) PEG1 modified with RGD (PEG1-RGD), (3) a looser network PEG hydrogel (PEG2), (4) PEG2 modified with RGD (PEG2-RGD), (5) a collagen membrane, and (6) a polylactide/polyglycolide/trimethylene carbonate membrane. The animals were sacrificed at 14 days. Histomorphometric analyses were performed on undecalcified Epon sections using a standardized region of interest. For statistical analysis, paired t-test and signed rank test were applied. Results: PEG1 and PEG1-RGD remained intact and maintained the shape. PEG2 and PEG2-RGD completely degraded and were replaced by connective tissue and bone. The largest amount of mineralized tissue was found for PEG2-RGD (21.4%), followed by PEG 2 (9.5%). The highest percentage of residual hydrogel/membrane was observed for PEG1-RGD (55.6%), followed by PEG1 (26.7%). Conclusions: Modifications of the physico-chemical properties of PEG hydrogels and the addition of RGD influenced soft and hard tissue integration and biodegradation. PEG1 showed an increased degradation time and maintained the shape. The soft tissue integration was enhanced by adding an RGD sequence. A high turn-over rate and extensive bone regeneration was observed using PEG2. The addition of RGD further improved bone formation and soft tissue integration. To cite this article: Thoma DS, Subramani K, Weber FE, Luder HU, Hämmerle CHF, Jung RE. Biodegradation, soft and hard tissue integration of various polyethylene glycol hydrogels: a histomorphometric study in rabbits. Clin. Oral Impl. Res. 22, 2011; 1247-1254. doi: 10.1111/j.1600-0501.2010.02075.x [ABSTRACT FROM AUTHOR]

Abstract: The negative cost cycle detection (NCCD) problem in weighted directed graphs is a fundamental problems in theoretical computer science with applications in a wide range of domains ranging from maximum flows to image segmentation. From the perspective of program verification, this problem is identical to the problem of checking the satisfiability of a conjunction of difference constraints. There exist a number of approaches in the literature for NCCD with each approach having its own set of advantages. Recently, a greedy, space-efficient algorithm called the stressing algorithm was proposed for this problem. In this paper, we present a novel proof of the Stressing algorithm and its verification using the Prototype Verification System (PVS) theorem prover. This example is part of a larger research program to verify the soundness and completeness of a core set of decision procedures. [Copyright &y& Elsevier]

In this paper, we propose a simple randomized algorithm for the NAE2SAT problem. The analysis of the algorithm uses the theory of symmetric, absorbing random walks. Inasmuch as the NAE2SAT problem is in the complexity class L (Deterministic Logarithmic Space) and L ⊆ P ⊆ RP, the existence of such an algorithm is not surprising. However, the simplicity of our approach and the insights revealed by its analysis make the current study worthwhile. Not-all-equal SAT (NAESAT) is the variant of the satisfiability problem (SAT), in which we are interested in an assignment that satisfies all the clauses, but falsifies at least one literal in each clause. NAESAT is an interesting SAT variant in its own right and has been studied by SAT theoreticians, on account of its connections to the graph colouring problem. It is well-known that the variant of NAESAT with exactly three literals per clause (NAE3SAT) is NP-complete [M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman Company, San Francisco, 1979]. Likewise, there seem to be a number of polynomial time algorithms for NAE2SAT as part of algorithm design folklore [D.S. Johnson, Personal Communication]. Here we show that the NAE2SAT problem admits an extremely simple, literal-flipping algorithm, in precisely the same way that 2SAT does. On a satisfiable instance involving n variables, the probability that our algorithm does not find a satisfying assignment is at most 1/24. The randomized algorithm takes O(1) extra space, in the presence of a verifier and provides an interesting insight into checking whether a graph is bipartite. It must be noted that space-parsimonious randomized algorithms for a problem, such as the one proposed in this paper, invariably lead to error-bounded, online algorithms for the same. As part of our analysis, we argue that a restricted variant of NAE2SAT is L-complete. We note that the bounds derived in this paper are sharper than the ones in Papadimitriou [C.H. Papadimitriou, On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, IEEE, ed., IEEE, Washington, DC, 1991, pp. 163-169]. [ABSTRACT FROM AUTHOR]

The single source shortest paths problem with positive edge weights (SSSPP) is one of the more widely studied problems in operations research and theoretical computer science, on account of its wide applicability to practical situations. This problem was first solved in polynomial time by Dijkstra, who showed that by extracting vertices with the smallest distance from the source and relaxing its outgoing edges, the shortest path to each vertex is obtained. Variations of this general theme have led to a number of algorithms which work well in practice. At the heart of a Dijkstra implementation is the technique used to implement a priority queue. It is well known that using Dijkstra's approach requires Ω( n log n) steps on a graph having n vertices, since it essentially sorts vertices based on their distances from the source. Accordingly, the fastest implementation of Dijkstra's algorithm on a graph with n vertices and m edges should take Ω( m + n · log n) time, and consequently, the Dijkstra procedure for SSSPP using Fibonacci Heaps is optimal in the comparison-based model. In this paper, we introduce a new data structure to implement priority queues called two-level heap (TLH) and a new variant of Dijkstra's algorithm called Phased Dijkstra. We contrast the performance of Dijkstra's algorithm (both the simple and the phased variants) using a number of data structures to implement the priority queue and empirically establish that TLH are far superior to Fibonacci heaps on every graph family considered. It is to be noted that our profiling includes both sparse and dense graphs. [ABSTRACT FROM AUTHOR]

Abstract: This paper discusses space–time tradeoffs associated with algorithms for the problem of detecting negative cost cycles in networks (NCCD). NCCD is one of the more ubiquitous problems in computer science and operations research, with applications ranging from program verification and real-time scheduling to image segmentation and shortest path identification. Typical algorithmic analysis, whether theoretical or empirical, focuses almost exclusively on the running time of the algorithm. However, there exist applications in which space is just as important a parameter as time is. This is especially true when the problem instances are very large, as is the case in program verification. Consequently, an algorithm that minimizes running time while ignoring the space overhead may be impractical. In this paper, we analyze a number of the more common algorithms for NCCD from the perspectives of both time and space, with a view towards providing a space–time tradeoff for the practitioner. All the algorithms discussed in this paper (with the exception of Network Simplex) run in time on a network with m arcs and n vertices; however, their space requirements range from (Stressing Algorithm) to (all the Bellman–Ford and Network Simplex variants). Our empirical results demonstrate that in the cases where space is paramount, the Stressing Algorithm is a useful alternative to the Bellman–Ford variants. [Copyright &y& Elsevier]

In this article, we introduce a Prover-Verifier model for analysing the computational complexity of a class of constraint satisfaction problems (CSPs) termed boolean binary constraint satisfaction problems (BBCSPs). BBCSPs represent an extremely general class of CSPs and find applications in a wide variety of domains including constraint programming, puzzle solving and program testing. The constraints in a BBCSP permit the combination of multiple theories as opposed to traditional constraint systems in which all constraints belong to the same theory. We establish that each instance of a BBCSP admits a coin-flipping Turing machine that halts in time polynomial in the size of the input. Furthermore, the algorithm is oblivious in that it never sees more than one constraint at a time. The prover, P, in the Prover-Verifier model is endowed with very limited powers. In particular, it has no memory and it can only pose restricted queries to the verifier. The verifier, on the other hand, is both omniscient in that it is cognisant of all the problem details and insincere in that it does not have to decide a priori on the intended proof. However, the verifier must stay consistent in its responses, i.e. it cannot rule out a certain possibility in one response to a query from the prover and then rule in the same possibility in response to a subsequent query. We note that the combination of the resources required by the prover and the type of certificate demanded of the verifier, determine the resources required by an algorithm. Inasmuch as our provers will be memoryless and our verifiers will be asked for extremely simple certificates, our work establishes the existence of a simple, randomised algorithm for BBCSPs. Our model itself serves as a basis for the design of zero-knowledge machine learning algorithms in that the prover ends up learning the proof desired by the verifier. Likewise, our work finds applications in the domain of certifying algorithm design, wherein the goal is to provide a proof of correctness of the algorithm on the input instance by providing an easily checkable certificate. [ABSTRACT FROM AUTHOR]

This paper is concerned with the design and analysis of a random walk algorithm for the 2CNF implication problem (2CNFI). In 2CNFI, we are given two 2CNF formulas $${\phi_{1}}$$ and $${\phi_{2}}$$ and the goal is to determine whether every assignment that satisfies $${\phi_{1}}$$ , also satisfies $${\phi_{2}}$$ . The implication problem is clearly coNP-complete for instances of kCNF, k ≥ 3; however, it can be solved in polynomial time, when k ≤ 2. The goal of this paper is to provide a Monte Carlo algorithm for 2CNFI with a bounded probability of error. The technique developed for 2CNFI is then extended to derive a randomized, polynomial time algorithm for the problem of checking whether a given 2CNF formula Nae-implies another 2CNF formula. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new randomized, partition-based algorithm for the problem of computing the number of inversion pairs in an unsorted array of n numbers. The algorithm runs in expected time O( n · log n) and uses O( n) extra space. The expected time analysis of the new algorithm is different from the analyses existing in the literature, in that it explicitly uses inversion pairs. The problem of determining the inversion pair cardinality of an array finds applications in a number of design domains, including but not limited to real-time scheduling and operations research. At the heart of our algorithm is a new inversion pair conserving partition procedure that is different from existing partition procedures such as Hoare-partition and Lomuto-partition. Although the algorithm is not fully adaptive, we believe that it is the first step towards the design of an adaptive, partition-based sorting algorithm whose running time is proportional to the number of inversion pairs in the input. [ABSTRACT FROM AUTHOR]

With the onset of distributed computing in hard real-time applications, the problem of assigning to, scheduling in, and executing jobs on processors, has received a lot of attention. Usually, real-time systems are embedded in closed loop reactive environments with uncertain behaviors and such systems take varying times to respond to such stimuli. One of the fundamental features of such systems is the presence of complex timing constraints between pairs of jobs. A secondary feature is the non-constant nature of the execution times of jobs. Real-time operating systems such as MARUTI can measure the interval within which the execution time varies (Mosse et al. In: Second IEEE Workshop on Experimental Distributed System, pp. 29–34., IEEE, 1990; Levi et al. 1989, ACM Special Interest Group Operat Syst 23(3):90–106). Partially clairvoyant scheduling was introduced in (Saksena, Parametric Scheduling in Hard Real-Time Systems. PhD thesis, University of Maryland, College Park, June 1994) to schedule jobs with varying execution times and non-trivial timing constraints. The schedulability of the job set is determined offline and a set of dispatch functions are produced from the given set of constraints if the job set is schedulable. The dispatch functions bind the start time of a job J to an interval that depends on the start and execution times of jobs sequenced before J. The online dispatcher of the system reads these dispatch functions and computes the interval within which a job can start without violating the constraints imposed on the system. In certain situations, the dispatcher fails to dispatch a job as the time to compute the dispatch functions associated with a job is greater than the interval within which the job needs to be dispatched. This phenomenon is called Loss of Dispatchability (Subramani, Duality in the Parametric Polytope and its Applications to a Scheduling Problem. PhD thesis, University of Maryland, College Park, August 2000). In this paper, we propose and implement a partially clairvoyant dispatching algorithm on a shared memory cluster with Concurrent Read Exclusive Write (CREW) architecture and contrast it with the sequential approach. For a preset number of processors, our approach has O(1) dispatch complexity while using a total of O( n 2) space, while the sequential approach requires Ω( n) time. The detailed implementation profile obtained clearly demonstrates the superiority of the multiprocessor approach to dispatching. We also address the issue of scalability of the dispatcher for increasing number of processors and show that job sets of different sizes require different number of processors. Finally, we demonstrate the effect of execution time on the dispatchability of schedules. [ABSTRACT FROM AUTHOR]

We contrast the performance of three algorithms for the problem of deciding whether a Partially Clairvoyant real-time system with relative timing constraints, as specified in the E-T-C scheduling framework, has a feasible schedule. In the E-T-C scheduling model, real-time scheduling problems are specified through a specialized class of constraint logic programs (CLPs) called Quantified Linear Programs (QLPs) [Subramani, K., 2003, An analysis of quantified linear programs. In: C.S. Calude (Ed.) Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS), volume 2731 of Lecture Notes in Computer Science, July (Springer-Verlag), pp. 265- 277]; thus algorithms for determining the schedulability of instances are procedures to determine the satisfiability of CLPs. Two of these algorithms, viz., the primal algorithm and the dual algorithm have already been discussed in the literature, while a third algorithm called the randomized dual algorithm has been recently proposed [Subramani, K. and Desovski, D. 2005, A new verification procedure for partially Clairvoyant scheduling. Proceedings of the 3rd International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS), October; Subramani, K. and Desovski, D., 2005, Out of order quantifier elimination for standard quantified linear programs, Journal of Symbolic Computation, 40, 1383-1396]. Our experiments demonstrate that the dual-based algorithms (i.e. the dual and the randomized dual) are more effective from an implementational perspective; this is surprising since all three algorithms have the same worst case asymptotic complexity. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present a comprehensive empirical analysis of the Vertex Contraction (VC) algorithm for the problem of checking whether a directed graph with positive and negative costs on its edges has a negative cost cycle (NCCD). VC was first presented in [K. Subramani, L. Kovalchick, Contraction versus relaxation: a comparison of two approaches for the negative cost cycle detection problem, in: P.M.A. Sloot et al. (Ed.), Proceedings of the third international conference on computational science (ICCS), Lecture notes in computer science, vol. 2659, Springer-Verlag, 2003, pp. 377–387] and is the only known purely greedy strategy for the NCCD problem. In [K. Subramani, L. Kovalchick, Contraction versus relaxation: a comparison of two approaches for the negative cost cycle detection problem, in: P.M.A. Sloot et al. (Ed.), Proceedings of the third international conference on computational science (ICCS), Lecture notes in computer science, vol. 2659, Springer-Verlag, 2003, pp. 377–387], we compared the performance profiles of a naive implementation of VC and the “standard” Bellman–Ford (BF) algorithm for negative cost cycle detection; we observed that VC performed an order of magnitude better than the BF algorithm. Our experiments were conducted on a range of randomly generated inputs over multiple classes of networks and the results conclusively demonstrated the superiority of VC over a naive implementation of BF. Our observations are surprising given that VC is asymptotically inferior to BF on sparse networks. This paper continues the study of contrasting greedy and dynamic programming (relaxation-based) approaches for the NCCD problem, by comparing sophisticated variants of VC with sophisticated implementations of the BF algorithm. Variants of VC are obtained by employing different heuristics to determine the vertex contraction sequence, in precisely the same manner as variants of BF are obtained by employing different heuristics to determine the edge relaxation sequence. Our experiments indicate that on most classes of networks, there is at least one VC variant with a performance profile that is comparable to the more sophisticated BF implementations. Our results are most surprising for the case of planar networks, where a variant of VC performs almost as well as the best relaxation-based algorithm. One of the principal conclusions of our work is that a simple, greedy approach involving vertex contraction is a good choice on sparse networks. On a more fundamental note, we establish that the selection of an algorithm for the NCCD problem should involve an analysis of the input and the architecture of the computing machine, in order to maximize performance. [Copyright &y& Elsevier]

Abstract: In this paper, we present an out of order quantifier elimination algorithm for a class of Quantified Linear Programs (QLPs) called Standard Quantified Linear Programs (SQLPs). QLPs in general and SQLPs in particular are extremely useful constraint logic programming structures that find wide applicability in the modeling of real-time schedulability specifications; see Subramani [Subramani, K., 2005a. A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. The Computer Journal 48 (3), 259–272]. Consequently any algorithmic advance in their solution has a strong practical impact. Prior to this work, the only known approaches to the solution of QLPs involved sequential variable elimination; see Subramani [Subramani, K., 2003b. An analysis of quantified linear programs. In: Calude, C.S. et al. (Eds.), Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science. DMTCS. In: Lecture Notes in Computer Science, vol. 2731. Springer-Verlag, pp. 265–277]. In the sequential approach, the innermost quantified variable is eliminated first, followed by the variable which then becomes the innermost quantified variable and so on, until we are left with a single variable from which the satisfiability of the original formula is easily deduced. This approach is applicable in both discrete and continuous domains; however, it is to be noted that the logic demanding the sequential approach requires that the variables are discrete-valued. To the best of our knowledge, the necessity for sequential elimination over continuous-valued variables has not been investigated in the literature. The techniques used in the development of our elimination algorithm may find applications in domains such as classical logic and finite model theory. The final aspect of our research concerns the structure-preserving nature of the algorithm that we introduce here; in general, it is not known whether discrete domains admit such elimination procedures. [Copyright &y& Elsevier]

In this paper we introduce a problem called Quantified Integer Programming, which generalizes the Quantified Satisfiability problem (QSAT). In a Quantified Integer Program (QIP) the program variables can assume arbitrary integral values, as opposed to the boolean values that are assumed by the variables of an instance of QSAT. QIPs naturally represent two-person integer matrix games. The Quantified Integer Programming problem is PSPACE-hard in general, since the QSAT problem is PSPACE-complete. Quantified Integer Programming can be thought of as a restriction of Presburger Arithmetic, in that we allow only conjunctions of linear inequalities. We focus on analyzing various special cases of the general problem, with a view to discovering subclasses that are tractable. Subclasses of the general QIP problem are obtained by restricting either the constraint matrix or quantifier specification or both. We show that if the constraint matrix is totally unimodular, the problem of deciding a QIP can be solved in polynomial time. We also establish the computational complexities of Oblivious strategy games and Clairvoyant strategy games. [ABSTRACT FROM AUTHOR]