Filtry
wszystkich: 262
-
Katalog
Wyniki wyszukiwania dla: tree
-
TREE PHYSIOLOGY
Czasopisma -
Tree-Ring Research
Czasopisma -
Tree Genetics & Genomes
Czasopisma -
The complexity of bicriteria tree-depth
PublikacjaThe tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...
-
The reliability of tree and star networks
PublikacjaThis paper investigated the reliability of tree and star networks. Following measures of network reliability are assumed: the expected number of nodes, that can communicate with the central node; the expected number of node pairs, that are connected by a path through the central node; the expected number of node pairs communicating.
-
The reliability of tree and star networks.
PublikacjaOne of the important parameters characterizing the quality of computer networks is the network's reliability with respect to failures of the communication links and nodes. This chapter investigated the reliability of tree and star networks. The tree and star topology is used in centralized computer networks. In centralized computer networks all communication must take place through some central computer. Following measures of network...
-
Perfect hashing tree automata
PublikacjaWe present an algorithm that computes a function that assigns consecutive integers to trees recognized by a deterministic, acyclic, finite-state, bottom-up tree automaton. Such function is called minimal perfect hashing. It can be used to identify trees recognized by the automaton. Its value may be seen as an index in some other data structures. We also present an algorithm for inverted hashing.Przedstawiamy algorytm, który oblicza...
-
A note on mixed tree coloring
PublikacjaZaproponowano liniowy algorytm dla problemu kolorowania mieszanego w drzewach, uzyskując tym samym poprawę w stosunku do algorytmu o złożoności O(n^2) podanego w pracy [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].
-
Lower bound on the domination number of a tree.
PublikacjaW pracy przedstawiono dolne ograniczenie na liczbę dominowania w drzewach oraz przedstawiono pełną charakterystykę grafów ekstremalnych.
-
An implementation of deterministic tree automata minimization
PublikacjaWstępujący, deterministyczny, skończony automat drzewiasty (DTA) może być używany jako struktura danych do przechowywania zbiorów nieuporządkowanych drzew bez narzuconej liczby poddrzew. Takie automaty są zwykle rzadsze niż automaty działające na napisach i dlatego należy zwrócić szczególną uwagę na ich wydajną minimalizację. W dostępnej literaturze jest jednak ciężko znaleźć proste i szczegółowe opisy procedury minimalizacji....
-
PLoS Currents-Tree of Life
Czasopisma -
On extremal sizes of locally k-tree graphs
PublikacjaA graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k>=0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k >= 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the...
-
Evaluation of the content of inorganic anions in tree saps
PublikacjaTree saps were once commonly used in the countries of Northern, Central and Eastern Europe. Although once almost forgotten, their popularity has been growing recently as part of an interest in organic food and traditional medicine. Tree saps, tapped mainly from birch and maple trees, are drunk both fresh and fermented or are used as raw material for the production of food products, e.g. syrups. The aim of this study was to determine...
-
Incremental construction of Minimal Tree Automata [online]
PublikacjaWe describe an algorithm that allows the incremental addition or removal of unranked ordered trees to minimal frontier-to-root deterministic tree automaton (DTA). The algorithm takes a tree t and a minimal DTA A as input; it outputs a minimal DTA A' which accepts the language L(A) accepted by A incremented (or decremented) with the tree t. The algorithm can be used to efficiently maintain dictionaries which store large collections...
-
Average Size of a Suffix Tree for Markov Sources
PublikacjaWe study a suffix tree built from a sequence generated by a Markovian source. Such sources are more realistic probabilistic models for text generation, data compression, molecular applications, and so forth. We prove that the average size of such a suffix tree is asymptotically equivalent to the average size of a trie built over n independentsequences from the same Markovian source. This equivalenceis only known for memoryless...
-
Bounds on the vertex-edge domination number of a tree
PublikacjaA vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4...
-
Lower bound on the paired domination number of a tree
PublikacjaW pracy przedstawione jest ograniczenie dolne dla liczby dominowania parami oraz scharakteryzowane są wszystkie drzewa ekstremalne.
-
Tool support for ECSDM fault tree methodology
PublikacjaExtended Common Safety Description Model (ECSDM) jest językiem do formalnej specyfikacji systemów związanych z bezpieczeństwem oraz ich komponentów. Język ten zawiera konstrukcje umożliwiające specyfikację zależności czasowych. Może on zostać użyty w analizie drzew błędów, aby uzyskać jednoznaczną specyfikację hazardów w sytuacji, gdy są one uzależnione od związków czasowych pomiędzy przyczynami. Artykuł opisuje narzędzie wytworzone...
-
Complexity of weak acceptonic conditions in tree automata
PublikacjaRozważano złożoność problemu pustości dla automatów na drzewach ze słabymi warunkami akceptowalności. Rozważano także translacje pomiędzy słabymi i silnymi warunkami akceptowalności.
-
MINERAL CONTENT OF TREE SAP FROM THE SUBCARPATHIAN REGION
Publikacjabut also as medicinal substance in folk medicine. Traditionally, it was used to treat various conditions, mostly anaemia and chronic fatigue. This study has been designed to establish the content of metallic elements (sodium, potassium, calcium, magnesium, zinc and copper) in sap collected from eight different species (silver birch, downy birch, hornbeam, Norway maple, boxelder maple, black walnut, black alder and white willow)...
-
Atmospheric deposition in coniferous and deciduous tree stands in Poland
PublikacjaThe objective of this study was to assess the transformation of precipitation in terms of quantity and chemical composition following contact with the crown layer in tree stands with varied species composition, to investigate the effect of four predominant forest-forming species (pine, spruce, beech, and oak) on the amount and composition of precipitation reaching forest soils, and to determine the sources of pollution in atmospheric...
-
Gossiping by energy-constrained mobile agents in tree networks
PublikacjaEvery node of an edge-weighted tree network contains a data packet. At some nodes are placed mobile agents, each one possessing an amount of energy (not necessarily the same for all agents). While walking along the network, the agents spend the energy proportionally to the distance traveled and collect copies of the data packets present at the visited network nodes. An agent visiting a node deposits there copies of all currently...
-
Lower bound on the weakly connected domination number of a tree
PublikacjaPraca dotyczy dolnego ograniczenia liczby dominowania słabo spójnego w drzewach (ograniczenie ze względu na ilość wierzchołków i ilość wierzchołków końcowych w drzewie).
-
Lower bound on the distance k-domination number of a tree
PublikacjaW artykule przedstawiono dolne ograniczenie na liczbę k-dominowania w drzewach oraz scharakteryzowano wszystkie grafy ekstremalne.
-
An algorithm for listing all minimal double dominating sets of a tree
PublikacjaWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
An Alternative Proof of a Lower Bound on the 2-Domination Number of a Tree
PublikacjaA 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in D has a at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. Fink and Jacobson [n-domination in graphs, Graph theory with applications to algorithms and computer science, Wiley, New York, 1985, 283-300] established the following lower bound on the 2-domination...
-
An upper bound on the total outer-independent domination number of a tree
PublikacjaA total outer-independent dominating set of a graph G=(V(G),E(G)) is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every tree T of order n >= 4, with l leaves and s support vertices we have...
-
An upper bound for the double outer-independent domination number of a tree
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)\D is independent. The double outer-independent domination number of a graph G, denoted by γ_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We prove...
-
A lower bound on the double outer-independent domination number of a tree
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)D is independent. The double outer-independent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We...
-
An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree
PublikacjaWe provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248n) . This implies that every tree has at most 1.3248 n minimal 2-dominating sets. We also show that this bound is tigh.
-
A lower bound on the total outer-independent domination number of a tree
PublikacjaA total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_t^{oi}(T) >= (2n-2l+2)/3,...
-
An upper bound on the 2-outer-independent domination number of a tree
PublikacjaA 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D, and the set V(G)D is independent. The 2-outer-independent domination number of a graph G, denoted by gamma_2^{oi}(G), is the minimum cardinality of a 2-outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_2^{oi}(T) <= (n+l)/2,...
-
Empirical analysis of tree-based classification models for customer churn prediction
PublikacjaCustomer churn is a vital and reoccurring problem facing most business industries, particularly the telecommunications industry. Considering the fierce competition among telecommunications firms and the high expenses of attracting and gaining new subscribers, keeping existing loyal subscribers becomes crucial. Early prediction of disgruntled subscribers can assist telecommunications firms in identifying the reasons for churn and...
-
Perfect hashing with pseudo-minimal bottom-up deterministic tree automata
PublikacjaWe describe a technique that maps unranked trees to their hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to techniques implemented with minimal tree automata, our procedure builds a pseudo-minimal DTA. Pseudo-minimal automata are larger than the minimal ones but in turn the mapping can be arbitrary, so it can be determined prior to the automaton construction. We also provide procedures to build incrementally...
-
A city is not a tree: a multi-city study on street network and urban life
PublikacjaChristopher Alexander, a British-American scholar, differentiated an old (natural) city from a new (planned) one by structure. The former resembles a “semilattice”, or a complex system encompassing many interconnected sub-systems. The latter is shaped in a graph-theoretical “tree”, which lacks the structural complexity as its sub-systems are compartmentalized into a single hierarchy. This structural distinction explains why, or...
-
Critical Case Stochastic Phylogenetic Tree Model via the Laplace Transform
PublikacjaBirth–and–death models are now a common mathematical tool to describe branching patterns observed in real–world phylogenetic trees. Liggett and Schinazi (2009) is one such example. The authors propose a simple birth–and–death model that is compatible with phylogenetic trees of both influenza and HIV, depending on the birth rate parameter. An interesting special case of this model is the critical case where the birth rate equals the...
-
A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves
PublikacjaW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.
-
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
PublikacjaW pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania....
-
Tree-based homogeneous ensemble model with feature selection for diabetic retinopathy prediction
Publikacja -
Multidimensional Feature Selection and Interaction Mining with Decision Tree Based Ensemble Methods
Publikacja -
INDIVIDUAL TREE DETECTION FROM UAV LIDAR DATA IN A MIXED SPECIES WOODLAND
Publikacja -
Fault Tree Analysis and Failure Diagnosis of Marine Diesel Engine Turbocharger System
Publikacja -
Construction of a picewise-linear classifier by applaing discriminant analysis to decision tree induction
PublikacjaArtykuł prezentuje metodę konstrukcji drzew decyzyjnych. W odróżnieniu od większości popularnych algorytmów, które wybierają pojedyncze cechy do budowy reguł decyzyjnych w węzłach drzewa, ta metoda łączy wszystkie cechy. Używa ona wieloklasowego kryterium Fishera do wydzielenia nowych cech, które są liniowa kombinacją cech pierwotnych. Takie drzewa mogą aproksymować złożone regiony decyzyjne używając mniejszej liczby węzłów w porównaniu...
-
Electrical Tree Growth Behavior Under AC and DC High Voltage in Power Cables
PublikacjaThis work investigates the impact of an applied AC and DC high voltage on the electrical tree behavior in extruded cross-linked polyethylene (XLPE) insulation based on simulation and experimental validation. Extensive partial discharge (PD) testing methods are being implemented for high voltage cables under AC voltage for monitoring their condition. However, these PD testing methods cannot be utilized for power cables under DC...
-
The partial-order tree: a new structure for indexing on complex attributes in object-oriented databases
Publikacja -
Adaptive neuro fuzzy and fuzzy decision tree classifiers as applied to sea floor characterization.
PublikacjaPrzedstawiono wyniki badań wpływu różnych parametrów echa odbitego od dna morskiego na dokładność klasyfikacji typu dna przy pomocy sieci neuronowej z logiką rozmytą i przy pomocy drzew decyzyjnych. W szczególności uwzględniono takie parametry echa jak: energia, amplituda i nachylenie opadającego zbocza, wzbogacone o współczynniki falkowe otrzymane z dyskretnej transformacji falkowej (DWT).
-
The energy consumption during the birch tree sap concentration process using the reverse osmosis system
PublikacjaBirch tree sap was concentrated by mens of the reversed osmosis technique. The energy consumption in a small-scale pilot apparatus was estimated. The threshold value for the water removal above which the specific energy consumption significantly increased was identified. Below the threshold value the reversed osmosis had low energy demand and could be an attractive method for the production of birch tree sap-based beverages.
-
Tree rings as an indicator of atmospheric pollutant deposition to subalpine spruce forests in the Sudetes (Southern Poland)
PublikacjaIn spite of their moderate altitude (1000–1600m a.s.l.), the Western SudetyMountains belong to areas with the most efficient fog precipitation in Europe. Intense industrial activity in the area of windward western foothills caused an exceptional intensification of atmospheric pollutant deposition via precipitation and fog to take place since the 1950s. In the second half of the 1970s a massive spruce forest dieback began affecting...
-
Family Tree for Aqueous Organic Redox Couples for Redox Flow Battery Electrolytes: A Conceptual Review
PublikacjaRedox flow batteries (RFBs) are an increasingly attractive option for renewable energy storage, thus providing flexibility for the supply of electrical energy. In recent years, research in this type of battery storage has been shifted from metal-ion based electrolytes to soluble organic redox-active compounds. Aqueous-based organic electrolytes are considered as more promising electrolytes to achieve “green”, safe, and low-cost...
-
A Fuzzy Event Tree Model for Accident Scenario Analysis of Ship Stuck in Ice in Arctic Waters
Publikacja -
Mean Shift Segmentation Assessment for Individual Forest Tree Delineation from Airborne Lidar Data
Publikacja -
Use of Bi-Temporal ALS Point Clouds for Tree Removal Detection on Private Property in Racibórz, Poland
PublikacjaTrees growing on private property have become an essential part of urban green policies. In many places, restrictions are imposed on tree removal on private property. However, monitoring compliance of these regulations appears difficult due to a lack of reference data and public administration capacity. We assessed the impact of the temporary suspension of mandatory permits on tree removal, which was in force in 2017 in Poland,...
-
Long-term changes in the Leucobryo-Pinetum community: interactions between the tree-stand, understorey and moss layer
Publikacja -
The effects of forest patch size and ownership structure on tree stand characteristics in a highly deforested landscape of central Poland
Publikacja -
Attitudes to tree removal on private properties in two Polish cities.
Dane BadawczeLarge cities are increasingly faced with declining urban tree cover and related problems, such as increased urban heat islands and flash floods. Reducing these phenomena increasingly has to rely on trees located on private property. However, to effectively engage private landowners on these issues, more attention must be paid to understanding their...
-
Attitudes to tree removal on private property in rural and urban Polish municipalities.
Dane BadawczeThe urban-rural divide is an important factor known to affect public opinion on issues related to environmental protection and management. The present data set allows for a deeper understanding of this issue with respect to policies dealing with tree removal on private property in two municipalities located in southern Poland: Racibórz (an urban municipality)...
-
Expression-based decision tree model reveals distinct microRNA expression pattern in pediatric neuronal and mixed neuronal-glial tumors
Publikacja -
Metabolic activity of tree saps of different origin towards cultured human cells in the light of grade correspondence analysis and multiple regression modeling
PublikacjaTree saps are nourishing biological media commonly used for beverage and syrup production. Although the nutritional aspect of tree saps is widely acknowledged, the exact relationship between the sap composition, origin, and effect on the metabolic rate of human cells is still elusive. Thus, we collected saps from seven different tree species and conducted composition-activity analysis. Saps from trees of Betulaceae, but not from...
-
Laxer Clinical Criteria for Gaming Disorder May Hinder Future Efforts to Devise an Efficient Diagnostic Approach: A Tree-Based Model Study
PublikacjaInternet Gaming Disorder (IGD) has been recognized in May 2013 and can be evaluated using the criteria developed by American Psychiatric Association (APA). The present study investigated the role each IGD criteria plays in diagnosing disordered gaming. A total of 3,377 participants (mean age 20 years, SD = 4.3 years) participated in the study. The data collected was scrutinized to detect patterns...
-
Proteomic analysis of stipe explants reveals differentially expressed proteins involved in early direct somatic embryogenesis of the tree fern Cyathea delgadii Sternb
Publikacja -
TreeCmp: Comparison of Trees in Polynomial Time
PublikacjaMetryki filogenetyczne umożliwiają ocenę jakości wyników analizy filogenetycznej oraz wiarygodności algorytmów przeprowadzających taką analizę. Aplikacja TreeCmp oferuje efektywne, wielomianowe implementacje ośmiu takich metryk (dla drzew nieukorzenionych i zawierających korzeń) zdefiniowanych dla dowolnych filogenez (nie koniecznie binarnych). Program ten jako pierwszy umożliwia wyznaczanie nowych metryk, definiowanych w oparciu...
-
Visual TreeCmp : Comprehensive Comparison of Phylogenetic Trees on the Web
Publikacja1. We present Visual TreeCmp—a package of applications for comparing phylogenetic tree sets. 2. Visual TreeCmp includes a graphical web interface allowing the visualization of compared trees and command line application extended by comparison methods recently proposed in the literature. 3. The phylogenetic tree similarity analysis in Visual TreeCmp can be performed using eighteen metrics, of which 11 are dedicated to rooted trees...
-
Modeling and Evaluation of Electric Treeing Phenomena in Polymeric Cable Insulation
PublikacjaThis paper investigates the treeing phenomenon in polymeric materials such as crosslinked polyethylene (XLPE) that is widely used in medium and high voltage power cables as primary insulation. The modeling of electrical tree growth in the insulation from its initiation to breakdown is significant research work that illustrates the discharge dynamics and its impact on aging process in polymeric insulation. This study utilizes pulse...
-
Forests Trees and Livelihoods
Czasopisma -
Trees Forests and People
Czasopisma -
TREES-STRUCTURE AND FUNCTION
Czasopisma -
Deviations of treeline Norway spruce radial growth from summer temperatures in East-Central Europe
Publikacja -
Preserving Trees in Automata
PublikacjaWe present a method to store additional information in a minimal automaton so that it is possible to compute a corresponding tree node number for a state. The number can then be used to retrieve additional information. The method works for minimal (and any other) deterministic acyclic finite state automata (DFAs). We also show how to compute the inverse mapping.
-
On the partition dimension of trees
PublikacjaGiven an ordered partition Π={P1,P2,…,Pt} of the vertex set V of a connected graph G=(V,E), the partition representation of a vertex v∈V with respect to the partition Π is the vector r(v|Π)=(d(v,P1),d(v,P2),…,d(v,Pt)), where d(v,Pi) represents the distance between the vertex vv and the set Pi. A partition Π of V is a resolving partition of G if different vertices of G have different partition representations, i.e., for every...
-
Paired bondage in trees
PublikacjaW pracy zdefiniowano pojęcie liczby zniewolenia parami jako moc najmniejszego zbioru krawędzi, którego usunięcie z grafu spowoduje wzrost liczby dominowania parami. W szczególności scharakteryzowane są wszystkie drzewa, w których liczba zniewolenia wynosi 0, czyli takie, w których usunięcie dowolnego podzbioru krawędzi nie zwiększy liczby dominowania parami.
-
Computer aided registration of current pulses in polyethylene insulation during the first stage of electrical treeing.
PublikacjaW referacie przedstawiono aplikację w programie Labview do automatycznej rejestracji impulsów prądowych zjawisku drzewienia elektrycznego w izolacji polietylenowej.
-
Minimal 2-dominating sets in Trees
PublikacjaWe provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3247^n). This leads to that every tree has at most 1.3247^n minimal 2-dominating sets. We also show that thisbound is tight.
-
Minimal double dominating sets in trees
PublikacjaWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
Total chromatic sum for trees
PublikacjaThe total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We provide infinite families of trees for which the minimum number of colors to achieve the total chromatic sum is equal to the total chromatic number. We construct infinite families of trees for which these numbers are not equal, disproving the conjecture from 2012.
-
Connected searching of weighted trees
PublikacjaW pracy pokazano, że problem spójnego przeszukiwania drzew ważonych jest silnie NP-zupełny. Problem pozostaje trudnym dla drzew z jednym wierzchołkiem o stopniu większym niż 2. Ponadto, przedstawiony został wielomianowy optymalny algorytm dla klasy drzew z ograniczonym stopniem.
-
Connected searching of weighted trees
PublikacjaW artykule rozważamy problem spójnego przeszukiwania drzew obciążonych. Autorzy w [L. Barriere i inni, Capture of an intruder by mobile agents, SPAA'02 (2002) 200-209] twierdzą, że istnieje wielomianowy algorytm dla problemu obliczania optymalnej strategii przeszukiwania obciążonego drzewa. W niniejszej pracy pokazano, że problem ten jest obliczeniowo trudny nawet dla wierzchołkowo-obciążonych drzew (wagi krawędzi równe 1) oraz...
-
The complexity of list ranking of trees
PublikacjaUporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa...
-
Reconfiguring Minimum Dominating Sets in Trees
PublikacjaWe provide tight bounds on the diameter of γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. In particular, we prove that for any tree T of order n ≥ 3, the diameter of its γ-graph is at most n/2 in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most 2(n − 1)/3. Our proof is constructive, leading to a simple linear-time algorithm for determining...
-
Trees having many minimal dominating sets
PublikacjaWe provide an algorithm for listing all minimal dominating sets of a tree of order n in time O(1.4656^n). This leads to that every tree has at most 1.4656^n minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds 1.4167^n, thus exceeding 2^{n/2}. This establishes a lower bound on the running time of an algorithm for listing all minimal dominating...
-
Construction of phylogenetic trees with topological constraints
PublikacjaThis paper proposes a method of reconstruction of phylogenetic trees based on heuristic search with topological constraints. Using topological constraints it is possible to reduce the set of solutions as well as to enforce that the result is consistent with a given hypothesis about the evolution process within some group of species. Along with this work a number of algorithms used for phylogenetic analysis were implemented. Those...
-
Total outer-connected domination in trees
PublikacjaW pracy przedstawiono dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego w grafach oraz scharakteryzowano wszystkie drzewa osiągające to ograniczenie.
-
Properties of the triset metric for phylogenetic trees
Publikacjathe 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.
-
Approximate search strategies for weighted trees
PublikacjaW pracy podajemy 3-przybliżony algorytm dla problemu spójnego przeszukiwania drzew ważonych.
-
Total restrained domination numbers of trees
PublikacjaOpisane są wszystkie drzewa, w których liczby dominowania totalnego i totalno - powściągniętego są sobie równe, a także podano dolne ograniczenie na liczbę dominowania totalno - powściągniętego w drzewach.
-
Analyzing sets of phylogenetic trees using metrics
PublikacjaThe reconstruction of evolutionary trees is one of the primary objectives in phylogenetics. Such a tree represents historical evolutionary relationships between different species or organisms. Tree comparisons are used for multiple purposes, from unveiling the history of species to deciphering evolutionary associations among organisms and geographical areas. In this paper, we describe a general method for comparing phylogenetictrees...
-
On trees attaining an upper bound on the total domination number
PublikacjaA total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. The total domination number of a graph G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [Total and paired-domination numbers of a tree, AKCE International Journal of Graphs and Combinatorics 1 (2004), 69-75] established the following upper bound on the total domination...
-
Collaborative Exploration of Trees by Energy-Constrained Mobile Robots
PublikacjaWe study the problem of exploration of a tree by mobile agents (robots) that have limited energy. The energy constraint bounds the number of edges that can be traversed by a single agent. We use a team of agents to collectively explore the tree and the objective is to minimize the size of this team. The agents start at a single node, the designated root of the tree and the height of the tree is assumed to be less than the energy...
-
Approximation Strategies for Generalized Binary Search in Weighted Trees
PublikacjaWe consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node t in a given tree T. Upon querying a node v of the tree, the strategy receives as a reply an indication of the connected component of T\{v} containing the target t. The cost of querying each node is given by a known non-negative weight function, and the considered objective is to minimize the total...
-
Isolation Number versus Domination Number of Trees
PublikacjaIf G=(VG,EG) is a graph of order n, we call S⊆VG an isolating set if the graph induced by VG−NG[S] contains no edges. The minimum cardinality of an isolating set of G is called the isolation number of G, and it is denoted by ι(G). It is known that ι(G)≤n3 and the bound is sharp. A subset S⊆VG is called dominating in G if NG[S]=VG. The minimum cardinality of a dominating set of G is the domination number, and it is denoted by γ(G)....
-
Polynomial triset metric for unrooted phylogenetic trees
Publikacjathe following paper presents a polynomial triset metric for unrooted phylogenetic trees (based on weighted bipartite graphs and the method of determining a minimum edge cover) and its basic characteristics. also a list of further directions of research and examples of the wider use of this metric is presented.
-
On a matching distance between rooted phylogenetic trees
PublikacjaThe 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...
-
Modeling of event trees for the rapid scenario development
PublikacjaThe paper concerns the safety of ships in abnormal/damage conditions. Some conclusions following from the research associated with development of a method for safety assessment of ships in abnormal/damage conditions is presented in the paper. The method called SSAMADC (Ship Safety Assessment Method in Abnormal/Damage Conditions) is a risk-based method and is connected with application of the quantitative risk assessment QRA approach....
-
Weakly connected domination stable trees [online]
PublikacjaPraca dotyczy pełnej charakteryzacji drzew stabilnych ze względu na liczbę dominowania słabo spójnego.
-
The effect of trees in the road crown on road safety
PublikacjaW referacie przedstawiono problem występowania wypadków związanych z najechaniem na drzewo. Problem ten występuje w Polsce głównie w województwach północnych i zachodnich, co jest związane ze specyficznymi cechami sieci drogowej tego obszaru. Referat przedstawia negatywny wpływ drzew rosnących w koronie drogi na bezpieczeństwo ruchu drogowego oraz określa metody zapobiegania wypadkom związanym z najechaniem na drzewo. Ze względu...
-
Total outer-connected domination numbers of trees
PublikacjaNiech G=(V,E) będzie grafem bez wierzchołków izolowanych. Zbiór wierzchołków D nazywamy zbiorem dominującym totalnym zewnętrznie spójnym jeżli każdy wierzchołek grafu ma sąsiada w D oraz podgraf indukowany przez V-D jest grafem spójnym. Moc najmniejszego zbioru D o takich własnościach nazywamy liczbą dominowania totalnego zewnątrznie spójnego. Praca m.in. zawiera dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego...
-
Why are trees still such a major hazard to drivers in Poland?
PublikacjaRoadside trees are one of Poland's most serious road safety issues. Since 2009 more than 2800 people have been killed as a result of tree collisions; this represents about 15% of all of Poland's accident fatalities between 2009 and 2013. In some of the country's regions striking a tree caused more than 30% of all road accident fatalities. With no proper regulations, guidelines or examples of good practice, roadside environments...
-
Time versus space trade-offs for randezvous in trees
PublikacjaTwo identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory...
-
Ranking ecosystem services delivered by trees in urban and rural areas
PublikacjaPolicies and strategies for tree management and protection on a national, regional, and local level have not sufficiently considered differences between rural and urban areas. We used expert knowledge to compare rural and urban areas in a case study evaluating the relative importance of ecosystem services (ES) in policy development. The Analytic Hierarchy Process (AHP) and focus group discussions were used to rank 17 ES, representing...
-
Edge-chromatic sum of trees and bounded cyclicity graphs
Publikacja -
Matching Split Distance for Unrooted Binary Phylogenetic Trees
Publikacja