Search
Filters
total: 39
Search results for: MINIMUM-WEIGHT PERFECT MATCHING
-
Comparing phylogenetic trees using a minimum weight perfect matching
PublicationA phylogenetic tree represents historical evolutionary relationshipbetween different species or organisms. There are various methods for reconstructing phylogenetic trees.Applying those techniques usually results in different treesfor the same input data. An important problem is to determinehow distant two trees reconstructed in such a wayare from each other. Comparing phylogenetic trees is alsouseful in mining phylogenetic information...
-
Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions
PublicationAbility to quantify dissimilarity of different phylogenetic trees describing the relationship between the same group of taxa is required in various types of phylogenetic studies. For example, such metrics are used to assess the quality of phylogeny construction methods, to define optimization criteria in supertree building algorithms, or to find horizontal gene transfer (HGT) events. Among the set of metrics described so far in...
-
On a matching distance between rooted phylogenetic trees
PublicationThe Robinson–Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach...
-
Properties of the triset metric for phylogenetic trees
Publicationthe following paper presents a new polynomial time metric for unrootedphylogenetic trees (based on weighted bipartite graphs and the method ofdetermining a minimum perfect matching) and its properties. also many its properties are presented.
-
All graphs with paired-domination number two less than their order
PublicationLet G=(V,E) be a graph with no isolated vertices. A set S⊆V is a paired-dominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number γp(G) of G is defined to be the minimum cardinality of a paired-dominating set of G. Let G be a graph of order n. In [Paired-domination in graphs, Networks 32 (1998), 199-206] Haynes and Slater...
-
Comparing Arbitrary Unrooted Phylogenetic Trees Using Generalized Matching Split Distance
PublicationIn the paper, we describe a method for comparing arbitrary, not necessary fully resolved, unrooted phylogenetic trees. Proposed method is based on finding a minimum weight matching in bipartite graphs and can be regarded as a generalization of well-known Robinson-Foulds distance. We present some properties and advantages of the new distance. We also investigate some properties of presented distance in a common biological problem...
-
Total domination in versus paired-domination in regular graphs
PublicationA subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...
-
Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number
PublicationGiven two types of graph theoretical parameters ρ and σ, we say that a graph G is (σ, ρ)- perfect if σ(H) = ρ(H) for every non-trivial connected induced subgraph H of G. In this work we characterize (γw, τ )-perfect graphs, (γw, α′)-perfect graphs, and (α′, τ )-perfect graphs, where γw(G), τ (G) and α′(G) denote the weakly connected domination number, the vertex cover number and the matching number of G, respectively. Moreover,...
-
A collection of directed graphs for the minimum cycle mean weight computation
Open Research DataThis dataset contains definitions of the 16 directed graphs with weighted edges that were described in the following paper: Paweł Pilarczyk, A space-efficient algorithm for computing the minimum cycle mean in a directed graph, Journal of Mathematics and Computer Science, 20 (2020), no. 4, 349--355, DOI: 10.22436/jmcs.020.04.08, URL: http://dx.doi.org/10.22436/jmcs.020.04.08 These...
-
Generalization of Phylogenetic Matching Metrics with Experimental Tests of Practical Advantages
PublicationThe ability to quantify a dissimilarity of different phylogenetic trees is required in various types of phylogenetic studies, for example, such metrics are used to assess the quality of phylogeny construction methods and to define optimization criteria in supertree building algorithms. In this article, starting from the already described concept of matching metrics, we define three new metrics for rooted phylogenetic trees. One...
-
Exact-match Based Wikipedia-WordNet Integration
PublicationAbility to link between WordNet synsets and Wikipedia articles allows usage of those resources by computers during natural language processing. A lot of work was done in this field, however most of the approaches focus on similarity between Wikipedia articles and WordNet synsets rather than creation of perfect matches. In this paper we proposed a set of methods for automatic perfect matching generation. The proposed methods were...
-
Exact modal absorbing boundary condition for waveguide simulations - discrete Green's function approach
PublicationA modal absorbing boundary condition (ABC) based on the discrete Green's function (DGF) is introduced and applied for termination of waveguides simulated by means of the finite-difference time-domain (FDTD) method. The differences between the developed approach and implementations already demonstrated in the literature are presented. By applying DGF, a consistent theoretical approach to modal ABC in the FDTD method is obtained....
-
The share of investments in gold and oil using the example of selected European stock exchanges– A comparative analysis
PublicationIn this article, optimal investment portfolios with minimal risk and maximum efficiency were calculated. The portfolios were designated for ten selected European stock exchanges, based on the listings of the twenty largest companies in each of those markets. All calculations were made based on company shares only, company shares and investments in gold, shares of companies and investments in crude oil as well as shares of companies...
-
Optimal edge-coloring with edge rate constraints
PublicationWe consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....
-
Nested Kriging Surrogates for Rapid Multi-Objective Optimization of Compact Microwave Components
PublicationA procedure for rapid EM-based multi-objective optimization of compact microwave components is presented. Our methodology employs a recently developed nested kriging modelling to identify the search space region containing the Pareto-optimal designs, and to construct a fast surrogate model. The latter permits determination of the initial Pareto set, further refined using a separate surrogate-assisted process. As an illustration,...
-
Weakly connected Roman domination in graphs
PublicationA Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...
-
Visual Lip Contour Detection for the Purpose of Speech Recognition
PublicationA method for visual detection of lip contours in frontal recordings of speakers is described and evaluated. The purpose of the method is to facilitate speech recognition with visual features extracted from a mouth region. Different Active Appearance Models are employed for finding lips in video frames and for lip shape and texture statistical description. Search initialization procedure is proposed and error measure values are...
-
NEW DESIGNS OF CENTRIFUGAL MAGNETIC FLUID SEALS FOR ROTATING SHAFTS IN MARINE TECHNOLOGY
PublicationThe centrifugal magnetic fluid seals have important advantage over the conventional centrifugal seals. They maintain very good sealing capacity at static, medium and high speeds of shaft rotation, with the increased seal lifetime, and minimum torque and static friction. These seals are particularly useful in cases when the angular shaft velocity varies and sometimes decreases to nearly or exactly zero, such as in flywheel applications,...
-
Secure Italian domination in graphs
PublicationAn Italian dominating function (IDF) on a graph G is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0, the total weight of f assigned to the neighbours of v is at least two, i.e., ∑u∈NG(v)f(u)≥2. For any function f:V(G)→{0,1,2} and any pair of adjacent vertices with f(v)=0 and u with f(u)>0, the function fu→v is defined by fu→v(v)=1, fu→v(u)=f(u)−1 and fu→v(x)=f(x) whenever x∈V(G)∖{u,v}. A secure Italian dominating...
-
Optimum Control of Gyroscopic Systems
PublicationThe problem of optimum control of transverse rotor vibrations with gyroscopic interactions has been described and solved in the paper. An integral performance index has been defined for such system in order to minimize vibration level of a chosen rotor point. For this reason, an efficient way of finding the weight coefficients of integral performance index for multi-degrees-of-freedom system with gyroscopic interactions has been...
-
Low-fidelity model considerations for simulation-based optimisation of miniaturised wideband antennas
PublicationHere, variable-fidelity electromagnetic (EM)-based design optimisation of miniaturised antennas is discussed. The authors focus on an appropriate selection of discretisation density of the low-fidelity EM model, which results in good performance of the optimisation algorithm in terms of its computational complexity and reliability. Trust-region gradient search with low-fidelity model corrected by means of non-linear frequency scaling...
-
On low-fidelity models for variable-fidelity simulation-driven design optimization of compact wideband antennas
PublicationThe paper addresses simulation-driven design optimization of compact antennas involving variable-fidelity electromagnetic (EM) simulation models. Comprehensive investigations are carried out concerning selection of the coarse model discretization density. The effects of the low-fidelity model setup on the reliability and computational complexity of the optimization process are determined using a benchmark set of three ultra-wideband...
-
Accelerated multi-objective design of miniaturized microwave components by means of nested kriging surrogates
PublicationDesign of microwave components is an inherently multiobjective task. Often, the objectives are at least partially conflicting and the designer has to work out a suitable compromise. In practice, generating the best possible trade‐off designs requires multiobjective optimization, which is a computationally demanding task. If the structure of interest is evaluated through full‐wave electromagnetic (EM) analysis, the employment of...
-
Application of linear buckling sensitivity analysis to economic design of cylindrical steel silos composed of corrugated sheets and columns
PublicationThe paper deals with global stability of steel cylindrical silos composed of corrugated walls and vertical columns with loads imposed by a bulk solid following Eurocode 1. The optimum silo design with respect to the steel weight was based on a sensitivity analysis method. The changes of silo column profiles at each design step were performed by means of influence lines for the buckling load factor due to the unit column bending...
-
Examination of fresh water chemistry in maritime Antarctica during austral summer 2017
PublicationDue to the fact that Antarctica is one of the least polluted places on Earth, it is a perfect place to observe the spread of global pollution. Therefore, research conducted on this continent is important due to the possibility of investigating the type of pollution and their way of transport. This work considers presence of organic contaminants in Maritime Antarctica in unexplored until now, Lions Rump headland. Qualitative and...
-
The Influence of the Cuboid Float’s Parameters on the Stability of a Floating Building
PublicationUsually, the concept of sufficient stability of a floating structure is connected with the capacity to keep a small heel angle despite the moment of heeling. The variable responsible for these characteristics is the initial metacentric height, which is the relation between the hydrostatic features of the pontoon and the mass properties of the entire object. This article answers the questions of how heavy the floating system should...
-
Study on Dry Sliding Wear and Friction Behaviour of Al7068/Si3N4/BN Hybrid Composites
PublicationHybrid aluminium metal matrix composites have the potential to replace single reinforced aluminium metal matrix composites due to improved properties. Moreover, tribological performance is critical for these composites, as they have extensive application areas, such as the automotive, aerospace, marine and defence industries. The present work aims to establish the tribological characteristics of Al7068/Si3N4/BN hybrid metal matrix...
-
How to meet when you forget: log-space rendezvous in arbitrary graphs
PublicationTwo identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result...
-
Size reduction of ultra-wideband antennas with efficiency and matching constraints
PublicationAntenna design is a multifaceted task that involves handling of various performance figures concerning both electrical performance of the structure as well as its geometry. Simultaneous control of several objectives through rigorous optimization is very challenging and virtually impossible through conventional approaches such as parameter sweeping. In this work, we investigate size reduction of ultra‐wideband antenna structures...
-
Simulation of the weight averaging of pulse frequency modulated sensor output signal
Open Research DataThe aim of the research is investigation of the efficiency of weight averaging of pulse frequency modulated signal. It was shown that from the point of view of the reduction of the sampling error the best are polynomial weighing functions, for which the maximum of this component error decreases proportionally to the appropriate power of the number of...
-
Measurements of raising of 160EC pantograph type
Open Research DataIn this description the results of the experiment and also simulation performed on the total assembly of the 160 EC pantograph type is given. Multibody dynamics of pantograph rising due to external torque and forces are measured for parameter validation of the pantograph model.
-
Reliable EM-driven size reduction of antenna structures by means of adaptive penalty factors
PublicationMiniaturization has become of paramount importance in the design of modern antenna systems. In particular, compact size is essential for emerging application areas such as internet of things, wearable and implantable devices, 5G technology, or medical imaging. On the other hand, reduction of physical dimensions generally has a detrimental effect on antenna performance. From the perspective of numerical optimization, miniaturization...
-
Brief Announcement: Energy Constrained Depth First Search
PublicationDepth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer B (e.g. due...
-
Study of a Multicriterion Decision-Making Approach to the MQL Turning of AISI 304 Steel Using Hybrid Nanocutting Fluid
PublicationThe enormous use of cutting fluid in machining leads to an increase in machining costs, along with different health hazards. Cutting fluid can be used efficiently using the MQL (minimum quantity lubrication) method, which aids in improving the machining performance. This paper contains multiple responses, namely, force, surface roughness, and temperature, so there arises a need for a multicriteria optimization technique. Therefore,...
-
Modeling by finite element methods of impact of erosion on frequency of normal modes of L-0 blade
PublicationAfter some time of exploitation steam turbine rotors blades in energetic industry they are being eroded and also their frequency of normal modes is changed. Those changes can cause to unwanted shift of blades normal mode frequencies. It is necessary to find quick method of rating changes of frequency in connection of mass loss due erosion. The evaluation of this dependence was made by finite element modeling method using HyperWorks...
-
Distributed graph searching with a sense of direction
PublicationIn this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function w provides for each vertex v the minimum number of searchers required to guard v, i.e., the fugitive may not pass through v without being detected only if at least w(v) searchers are present at v. This problem is a generalization of the classical edge searching problem, in which one has...
-
THE METHOD OF ANALYSIS OF DAMAGE REINFORCED CONCRETE BEAMS USING TERRESTRIAL LASER SCANNING
PublicationThe authors present an analysis of the possibility to assess deformations and mode of failure of R-C beams using terrestrial laser scanning. As part of experiments carried out at the Regional Laboratory of Construction (at Gdansk University of Technology), reinforced concrete beams were subjected to destruction by bending and by shear. The process of press impact on the reinforced concrete beam was recorded using terrestrial laser...
-
Medium-Voltage Drives: Challenges and existing technology
PublicationThe article presents an overview of state-of-art solutions, advances, and design and research trends in medium-voltage (MV) drive technologies - and also discusses the challenges and requirements associated with the use of such drives. The choice and deployment of MV drives in industries are associated with numerous requirements related to the front-end converter (grid side) and inverter (machine side). The focus is on solutions...
-
Nutrients, oxygen and suspended matter - Gdansk Deep (2001-2005)
Open Research DataThe results show short-term changes in the concentration of nutrients (nitrates, nitrites, ammonium ions, phosphates and total forms of nitrogen and phosphorus), dissolved oxygen and suspended particulate matter - SPM and its main components (organic carbon - POC, nitrogen - PON, phosphorus - TPP) in the water column of the Gdańsk Deep (Gdańsk Bay).