Academic literature on the topic 'Cycle graph C_n'

Recognizing graphs with high level of symmetries is hard in general, and usually requires additional structural understanding. In this paper we study a particular graph parameter and motivate its usage by devising eÿcient recognition algorithm for the family of I-graphs. For integers m a simple graph is cycle regular if every path of length ` belongs to exactly cycles of length m. We identify all cycle regular I-graphs and, as a conse-quence, describe linear recognition algorithm for the observed family. Similar procedure can be used to devise the recog-nition algorithms for Double generalized Petersen graphs and folded cubes. Besides that, we believe the structural observations and methods used in the paper are of independent interest and could be used for solving other algorithmic problems.

We develop a fixed-parameter tractable (FPT) algorithm for skeptical preferred reasoning in assumption-based argumentation (ABA). To this end we make use of so-called backdoors, i.e. sets of assumptions that need to be evaluated s.t. the remaining ABA framework (ABAF) belongs to a computational beneficial sub-class. In order to identify such target classes, we employ a suitable notion of a dependency graph of an ABAF. We show that these graphs can be constructed in polynomial time and that one can efficiently check sufficient properties ensuring that reasoning in the underlying ABAF is tractable. After establishing the theoretical foundations, we test our implementation against the ASPforABA solver which convincingly won the ABA track of the ICCMA'23 competition. As it turns out, our algorithm outperforms ASPforABA on instances with small backdoor sizes.

We study the problem of fair allocation of indivisible goods that form a graph and the bundles that are distributed to agents are connected subgraphs of this graph. We focus on the maximin share and the proportional fairness criteria. It is well-known that allocations satisfying these criteria may not exist for many graphs including complete graphs and cycles. Therefore, it is natural to look for approximate allocations, i.e., allocations guaranteeing each agent a certain portion of the value that is satisfactory to her. In this paper we consider the class of graphs of goods which do not contain a star with d+1 edges (where d > 1) as an induced subgraph. For this class of graphs we prove that there is an allocation assigning each agent a connected bundle of value at least 1/d of her maximin share. Moreover, for the same class of graphs of goods, we show a theorem which specifies what fraction of the proportional share can be guaranteed to each agent if the values of single goods for the agents are bounded by a given fraction of this share.

Abstract Due to new computer software tools and high speed personal computers, it is now possible to quickly analyze and optimize complex absorption heat pump cycles. These cycles utilize fluid mixtures and can have a large number of components. Absorption cycles are typically displayed on two-dimensional graphs, but these diagrams can cause confusion in understanding new cycle configurations and their potentials and limitations. This study uses three-dimensional graphs to create accurate representations of four cycles. In the advanced cycles, the many opportunities for internal heat recovery can be clearly seen. Additionally, the three-dimensional representations can justify the inclusion or removal of cycle components. They are an excellent tool for those new to the field to more quickly understand the cycles, and for those experienced with absorption to be innovative in developing new cycles.

Failure Modes and Effects Analysis (FMEA) is a useful tool to find possible flaws, to reduce cost and to shorten research cycle in complex industrial systems. Fault Tree Analysis (FTA) has gained credibility over the past years, not only in nuclear industry, but also in other industries like aerospace, petrochemical, and weapon. Both FMEA and FTA are effective techniques in safety analysis, but there are still many uncertain factors in them that are not well addressed until now. This paper combines FMEA and FTA based on Dynamic Uncertain Causality Graph (DUCG) to solve this issue. Firstly, the FMEA model is mapped into a corresponding DUCG graph. Secondly, FTA model is mapped into a corresponding DUCG graph. Thirdly, combine the above DUCG graphs. Finally, users can modify the combined DUCG graph and calculations are made. This paper bridges the gap between FMEA and FTA by combining the two methods using DUCG. And additional modeling power and analytical power can be achieved with the advantages of the combined DUCG safety analysis model and its inference algorithm. This method can also promote the application of DUCG in the system reliability and safety analysis. An example is used to illustrate this method.

The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended to the setting when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connected subgraph. Researchers proved that, unlike in the original problem (which corresponds to the case of the complete graph in the extended setting), in the case of the goods-graph being a tree, allocations offering each agent a bundle of or exceeding her maximin share value always exist. Moreover, they can be found in polynomial time. We consider here the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide results on allocations guaranteeing each agent a certain portion of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.

Abstract Product performance, variety, manufacturability, logistics and life cycle ultimately depend upon product architecture. Product architecture includes both the foundations and building blocks upon which a mechanical system is conceived. It is a key element of Design for Manufacture (DFM). Until recently relatively little work has been done to fully understand these ramifications. A first step toward this goal is to better quantify the attributes of product architecture for mechanical assemblies. Using interaction graphs and the mathematics of graph theory, this paper proposes metrics for evaluating product architecture. These metrics can be developed from information derived from the geometric design domain based upon part connectivity and joint strengths.

Mesh, hypercube, HHN, bubbls-sort, star, transposition, and macro-star graphs have been proposed as interconnection networks used in high-performance parallel computer structures. A hypercube expresses a node with n binary numbers, and has an edge between 1-bit other nodes. A hypercube is an excellent network from a graph-theoretic point of view, such as node symmetry, fault tolerance, recursive scalability, and Hamiltonian cycles. However, compared to the increase in the number of nodes, the number of edges increases proportionally, so the network cost is not good. The HHN graph was proposed as a network that improved the network cost by improving the disadvantages of the hypercube. HHN graph uses hypercube as a basic module. The HHN graph is a network that has improved network cost by designing it to have a hierarchical structure based on a hypercube. HHN graphs have a simple routing algorithm with fewer branches and fewer links than hypercubes. Although HHN's routing algorithm has a simple advantage, it has a disadvantage that the path length is long via unnecessary nodes. In this study, we propose a new routing algorithm that improves the path length of the HHN graph and analyze its efficiency. The improved routing algorithm proposed in this study has the result of improving the existing algorithm by 30% on average. In addition, we analyze the embedding of one interconnection network into another is a very important issue in the design and analysis of parallel algorithms. Through such embeddings the algorithms originally developed for one architecture can be directly mapped to another architecture. This paper describes novel methods for the embedding of hierarchical Hypercube networks in the hypercube to minimize the dilation and the expansion costs.

The conversion of heat into electricity, generally speaking heat-to-power generation, is a wide area of technologies and applications. This paper focuses on available systems, excepted the internal combustion cycles, applied to transform (waste) heat to power. Data of referenced market proved or time-to-market technologies are presented. A database of more than 1100 references has been built. The following categories can be found: Rankine Cycle plant, Organic Rankine Cycle plant, Steam engine, Kalina Cycle plant, Brayton cycle plant, micro gas turbine, closed cycle gas turbine plant, combined cycle gas turbine plant, Stirling engine, Ericsson engine and thermoelectric generator. We intentionally target a range of power from Watts to hundreds of MW, covering the range of temperature [80–1000°C] usually addressed by these systems. The comparison of performances is hereby discussed and compared to thermodynamic principles and theoretical results in the graph Maximum temperature [°C] versus Thermodynamic efficiency. Comparison with Carnot and Chambadal-Novikov-Curzon-Ahlborn efficiencies are performed. A more original contribution is the presentation of the graph Power [W] versus Thermodynamic efficiency. The analysis reveals a monotonous trend inside each technology. Furthermore this general behavior covers a very wide range of power, including technological transitions. Finally, the position of each technology in the map Maximum temperature [°C] versus Power [W] is also analyzed. Explanations based on thermodynamics and techno-economic approaches are proposed.

The Dual Cycle Elimination method was proposed by Mu¨ller-Hannemann for hexahedral mesh generation. The method begins with a surface quadrilateral mesh whose dual cycles have no self-intersections and, after the elimination of dual cycles, a hexahedral mesh is generated while tracing back the reverse order of eliminations and supplementing hexahedrons inside the object step by step. This paper presents the Characteristic Topology Method as a means to prescribe a quadrilateral surface mesh that can be initial data for further hexahedral mesh generation. The goal of this method is to stress the topology of the given surface and thus use construction of the loops within the algorithm. The surface is given in a nodal polygonal model and then decomposed into a triangle-quadrilateral model. Templates are used to determine the loops. Then due to some rules every loop is implemented by special additional Dual Cycles. The total mesh is the dual graph to the graph of dual cycles. The problem of self-intersections that may appear comes from Mu¨ller-Hannemann’s approach stated above and that is also implemented in this work as a sketch.

In a previous report we have investigates subsumption in the presence of terminological cycles for the description logic EL, which allows conjunctions, existential restrictions, and the top concept, and have shown that the subsumption problem remains polynomial for all three types of semantics usually considered for cyclic definitions in description logics. This result depends on a characterization of subsumption through the existence of certain simulation relations on the graph associated with a terminology. In the present report we will use this characterization to show how the most specific concept and the least common subsumer can be computed in EL with cyclic definitions. In addition, we show that subsumption in EL (with or without cyclic definitions) remains polynomial even if one adds a certain restricted form of global role-value-maps to EL. In particular, this kind of role-value-maps can express transitivity of roles.

In two previous papers we have investigates the problem of computing the least common subsumer (lcs) and the most specific concept (msc) for the description logic EL in the presence of terminological cycles that are interpreted with descriptive semantics, which is the usual first-order semantics for description logics. In this setting, neither the lcs nor the msc needs to exist. We were able to characterize the cases in which the lcs/msc exists, but it was not clear whether this characterization yields decidability of the existence problem. In the present paper, we develop a common graph-theoretic generalization of these characterizations, and show that the resulting property is indeed decidable, thus yielding decidability of the existence of the lcs and the msc. This is achieved by expressing the property in monadic second-order logic on infinite trees. We also show that, if it exists, then the lcs/msc can be computed in polynomial time.

Several grape varieties and red wines were found to contain large concentration of phenolic compounds which work as antioxidant in-vitro and in-vivo. Wastes from wine production contain antioxidants in large amounts, between 2-6% on dry material basis. Red wines but also white wines were found to prevent lipid peroxidation of turkey muscle tissues stored at 5oC. The antioxidant reaction of flavonoids found in red wines against lipid peroxidation were found to depend on the structure of the molecule. Red wine flavonoids containing an orthodihydroxy structure around the B ring were found highly active against LDL and membrane lipid peroxidation. The antioxidant activity of red wine polyphenols were also found to be dependent on the catalyzer used. In the presence of H2O2-activated myoglobin, the inhibition efficiency was malvidin 3-glucoside>catechin>malvidin>resveratol. However, in the presence of an iron redox cycle catalyzer, the order of effectiveness was resveratol>malvidin 3-glucoside = malvidin>catechin. Differences in protein binding were found to affect antioxidant activity in inhibiting LDL oxidation. A model protein such as BSA, was investigated on the antioxidant activity of phenolic compounds, grape extracts, and red wines in a lecithin-liposome model system. Ferulic acid followed by malvidin and rutin were the most efficient in inhibiting both lipid and protein oxidation. Catechin, a flavonal found in red-wines in relatively high concentration was found to inhibit myoglobin catalyzed linoleate membrane lipid peroxidation at a relatively very low concentration. This effect was studied by the determination of the by-products generated from linoleate during oxidation. The study showed that hydroperoxides are catalytically broken down, not to an alcohol but most probably to a non-radical adduct. The ability of wine-phenolics to reduce iron and from complexes with metals were also demonstrated. Low concentration of wine phenolics were found to inhibit lipoxygenase type II activity. An attempt to understand the bioavailability in humans of antocyanins from red wine showed that two antocyanins from red wine were found unchanged in human urine. Other antocyanins seems to undergo molecular modification. In hypercholesterolemic hamsters, aortic lipid deposition was significantly less in animals fed diets supplemented with either catechin or vitamin E. The rate of LDL accumulation in the carotid arteries was also significantly lower in the catechin and vitamin E animal groups. These results suggested a novel mechanism by which wine phenolics are associated with decreased risk of coronary heart diseases. This study proves in part our hypothesis that the "French Paradox" could be explained by the action of the antioxidant effects of phenolic compounds found at high concentration in red wines. The results of this study argue that it is in the interest of public health to increase the consumption of dietary plant falvonoids. Our results and these from others, show that the consumption of red wine or plant derived polyphenolics can change the antioxidant tone of animal and human plasma and its isolated components towards oxidative reactions. However, we need more research to better understand bioavailability and the mechanism of how polyphenolics affect health and disease.

Macroeconomic summary Annual inflation continued to rise in the first quarter (8.5%) and again outpaced both market expectations and the technical staff’s projections. Inflation in major consumer price index (CPI) baskets has accelerated year-to-date, rising in March at an annual rate above 3%. Food prices (25.4%) continued to contribute most to rising inflation, mainly affected by a deterioration in external supply and rising costs of agricultural inputs. Increases in transportation prices and in some utility rates (energy and gas) can explain the acceleration in regulated items prices (8.3%). For its part, the increase in inflation excluding food and regulated items (4.5%) would be the result of shocks in supply and external costs that have been more persistent than expected, the effects of indexation, accumulated inflationary pressures from the exchange rate, and a faster-than-anticipated tightening of excess productive capacity. Within the basket excluding food and regulated items, external inflationary pressures have meaningfully impacted on goods prices (6.4%), which have been accelerating since the last quarter of 2021. Annual growth in services prices (3.8%) above the target rate is due primarily to food away from home (14.1%), which was affected by significant increases in food and utilities prices and by a rise in the legal monthly minimum wage. Housing rentals and other services prices also increased, though at rates below 3%. Forecast and expected inflation have increased and remain above the target rate, partly due to external pressures (prices and costs) that have been more persistent than projected in the January report (Graphs 1.1 and 1.2). Russia’s invasion of Ukraine accentuated inflationary pressures, particularly on international prices for certain agricultural goods and inputs, energy, and oil. The current inflation projection assumes international food prices will increase through the middle of this year, then remain high and relatively stable for the remainder of 2022. Recovery in the perishable food supply is forecast to be less dynamic than previously anticipated due to high agricultural input prices. Oil prices should begin to recede starting in the second half of the year, but from higher levels than those presented in the previous report. Given the above, higher forecast inflation could accentuate indexation effects and increase inflation expectations. The reversion of a rebate on value-added tax (VAT) applied to cleaning and hygiene products, alongside the end of Colombia’s COVID-19 health emergency, could increase the prices of those goods. The elimination of excess productive capacity on the forecast horizon, with an output gap close to zero and somewhat higher than projected in January, is another factor to consider. As a consequence, annual inflation is expected to remain at high levels through June. Inflation should then decline, though at a slower pace than projected in the previous report. The adjustment process of the monetary policy rate wouldcontribute to pushing inflation and its expectations toward the target on the forecast horizon. Year-end inflation for 2022 is expected to be around 7.1%, declining to 4.8% in 2023. Economic activity again outperformed expectations. The technical staff’s growth forecast for 2022 has been revised upward from 4.3% to 5% (Graph 1.3). Output increased more than expected in annual terms in the fourth quarter of 2021 (10.7%), driven by domestic demand that came primarily because of private consumption above pre-pandemic levels. Investment also registered a significant recovery without returning to 2019 levels and with mixed performance by component. The trade deficit increased, with significant growth in imports similar to that for exports. The economic tracking indicator (ISE) for January and February suggested that firstquarter output would be higher than previously expected and that the positive demand shock observed at the end of 2021 could be fading slower than anticipated. Imports in consumer goods, retail sales figures, real restaurant and hotel income, and credit card purchases suggest that household spending continues to be dynamic, with levels similar to those registered at the end of 2021. Project launch and housing starts figures and capital goods import data suggest that investment also continues to recover but would remain below pre-pandemic levels. Consumption growth is expected to decelerate over the year from high levels reached over the last two quarters. This would come amid tighter domestic and external financial conditions, the exhaustion of suppressed demand, and a deterioration of available household income due to increased inflation. Investment is expected to continue to recover, while the trade deficit should tighten alongside high oil and other export commodity prices. Given all of the above, first-quarter economic growth is now expected to be 7.2% (previously 5.2%) and 5.0% for 2022 as a whole (previously 4.3%). Output growth would continue to moderate in 2023 (2.9%, previously 3.1%), converging similar to long-term rates. The technical staff’s revised projections suggest that the output gap would remain at levels close to zero on the forecast horizon but be tighter than forecast in January (Graph 1.4). These estimates continue to be affected by significant uncertainty associated with geopolitical tensions, external financial conditions, Colombia’s electoral cycle, and the COVID-19 pandemic. External demand is now projected to grow at a slower pace than previously expected amid increased global inflationary pressures, high oil prices, and tighter international financial conditions than forecast in January. The Russian invasion of Ukraine and its inflationary effects on prices for oil and certain agricultural goods and inputs accentuated existing global inflationary pressures originating in supply restrictions and increased international costs. A decline in the supply of Russian oil, low inventory levels, and continued production limits on behalf of the Organization of Petroleum Exporting Countries and its allies (OPEC+) can explain increased projected oil prices for 2022 (USD 100.8/barrel, previously USD 75.3) and 2023 (USD 86.8/barrel, previously USD 71.2). The forecast trajectory for the U.S. Federal Reserve (Fed) interest rate has increased for this and next year to reflect higher real and expected inflation and positive performance in the labormarket and economic activity. The normalization of monetary policy in various developed and emerging market economies, more persistent supply and cost shocks, and outbreaks of COVID-19 in some Asian countries contributed to a reduction in the average growth outlook for Colombia’s trade partners for 2022 (2.8%, previously 3.3%) and 2023 (2.4%, previously 2.6%). In this context, the projected path for Colombia’s risk premium increased, partly due to increased geopolitical global tensions, less expansionary monetary policy in the United States, an increase in perceived risk for emerging markets, and domestic factors such as accumulated macroeconomic imbalances and political uncertainty. Given all the above, external financial conditions are tighter than projected in January report. External forecasts and their impact on Colombia’s macroeconomic scenario continue to be affected by considerable uncertainty, given the unpredictability of both the conflict between Russia and Ukraine and the pandemic. The current macroeconomic scenario, characterized by high real inflation levels, forecast and expected inflation above 3%, and an output gap close to zero, suggests an increased risk of inflation expectations becoming unanchored. This scenario offers very limited space for expansionary monetary policy. Domestic demand has been more dynamic than projected in the January report and excess productive capacity would have tightened more quickly than anticipated. Headline and core inflation rose above expectations, reflecting more persistent and important external shocks on supply and costs. The Russian invasion of Ukraine accentuated supply restrictions and pressures on international costs. This partly explains the increase in the inflation forecast trajectory to levels above the target in the next two years. Inflation expectations increased again and are above 3%. All of this increased the risk of inflation expectations becoming unanchored and could generate indexation effects that move inflation still further from the target rate. This macroeconomic context also implies reduced space for expansionary monetary policy. 1.2 Monetary policy decision Banco de la República’s board of directors (BDBR) continues to adjust its monetary policy. In its meetings both in March and April of 2022, it decided by majority to increase the monetary policy rate by 100 basis points, bringing it to 6.0% (Graph 1.5).