Filtry
wszystkich: 1248
wybranych: 873
Wyniki wyszukiwania dla: bounded-degree graphs
-
Some results concerning the complexity of restricted colorings of graphs
Publikacja -
Processing of musical metadata employing Pawlak's flow graphs.
PublikacjaW artykule przedstawiono problemy wyszukiwania informacji muzycznej. W eksperymentach posłużono się meta opisem oraz wykorzystano metodę grafów przepływowych Pawlaka. Opisano skonstruowaną bazę nagrań muzycznych. Słowa kluczowe: meta opis, wyszukiwanie informacji muzycznej, baza danych muzycznych
-
Music Archive Metadata Processing Based on Flow Graphs.
PublikacjaW referacie zaproponowano metodykę wyszukiwania informacji muzycznej w bazach internetowych w oparciu o meta opis. Skonstruowany algorytm wykorzystuje grafy przepływowe Pawlaka.
-
An approximation algorithm for maximum P3-packing in subcubic graphs
PublikacjaW pracy podano algorytm 4/3-przyliżony dla trudnego obliczeniowo problemu umieszczania wierzchołkowo rozłącznych dwukrawędziowych ścieżek w grafach o stopniu maksymalnym 3 i stopniu minimalnym 2. Poprawiono tym samym wcześniejsze wyniki dla grafów kubicznych (A. Kelmans, D. Mubayi, Journal of Graph Theory 45, 2004).
-
A note on compact and compact circular edge-colorings of graphs
PublikacjaW pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...
-
Ramsey numbers for triangles versus almost-complete graphs.
PublikacjaPokazano, że w każdym krawędziowym pokolorowaniu dwoma kolorami grafu pełnego o 38 wierzchołkach występuje trójkąt w pierwszym kolorze lub podgraf izomorficzny z K_10 - e w drugim kolorze. Stąd otrzymujemy górne oszacowanie R(K_3, K_10 - e) <= 38. Przedstawiamy także pokolorowanie krawędziowe grafu K_36, którego istnienie dowodzi, że R(K_3, K_10 - e) >= 37.
-
Domination numbers in graphs with removed edge or set of edges
PublikacjaW artykule przedstawiony jest wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania spójnego i słabo spójnego.
-
Total domination in versus paired-domination in regular graphs
PublikacjaA 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...
-
Graphs with equal domination and 2-distance domination numbers
PublikacjaW publikacji scharakteryzowane są wszystkie te drzewa i grafy jednocykliczne, w których liczba dominowania oraz liczba 2-dominowania na odległość są sobie równe.
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublikacjaIn the following paper it will be presented a new model for analysis (in polynomial time) of the effectiveness of the guard systems. Therewill be presented its practical applications in problems such as searching for the weakest points of the system, planning guards' paths or cameras deployment, switching image from multiple cameras on several monitors, or interception of the intruder. This model is based on describing the guarded...
-
Application of BN in Risk Diagnostics Arising from the Degree of Urban Regeneration Area Degradation
PublikacjaUrban regeneration as a complex project, generates many extremely specific threats affecting the increase of investment risk. Its unique nature causes that probability parameter, normally applied in the process of risk quantification, is extremely difficult to estimate. Due to lack of historical data urban regeneration related activities are therefore associated with uncertainty. According to the authors, a useful tool for resolving...
-
Changing the Ship Propulsion System Performances Induced by Variation in Reaction Degree of Turbocharger Turbine
PublikacjaArtykuł przedstawia szczegółowy model matematyczny układu napędu statku obejmującego: wolnoobrotowy silnik spalinowy okrętowy, śruba okrętowa oraz regulator prędkości kątowej. Model ten, następnie jest wykorzystany do badania symulacyjnego zachowania układu zarówno w stanach ustalonych jak i nieustalonych. Model jest zweryfikowany z wynikami eksperymentalnymi. Przedstawienie oryginalnej metody oceny wrażliwości układu względem...
-
On reliability assessment of ship machinery system in different autonomy degree; A Bayesian-based approach
PublikacjaAnalyzing the reliability of autonomous ships has recently attracted attention mainly due to epistemic uncertainty (lack of knowledge) integrated with automatic operations in the maritime sector. The advent of new random failures with unrecognized failure patterns in autonomous ship operations requires a comprehensive reliability assessment specifically aiming at estimating the time in which the ship can be trusted to be left unattended....
-
Results of acoustic emission tests of corrosion protection degree of ship steel tanks covered by means of protective coatings (Phase I)
PublikacjaThis paper presents methods and results of the 1st series of tests of acoustic emission (AE) signals, aimed at assessing degree of corrosion protection of a tank made of hull structural steel, protected by means of a protective coating combined from polyurethane layer and concrete filler. The tests were carried outin compliance with a method specially elaborated for application to the work in question. In the method were used requirements...
-
Softly switched robustly feasible mpc for constrained linear systems under set bounded uncertainty- LQ-MPC with IC action
PublikacjaNie jest możliwe efektywne sterowanie procesem w szerokim zakresie zmian warunków operacyjnych przy użyciu jednego uniwersalnego regulatora. W pracy zaproponowano koncepcję sposobu regulacji polegającego na przełączaniu wielu regulatorów uzależnionego od stanu operacyjnego systemu. Często twarde przełączanie regulatorów nie jest pożądane lub wręcz możliwe, alternatywą jest ich miękkie przełączanie. W pracy rozważany jest problem...
-
Application of social relation graphs for early detection of transient spammers
PublikacjaWczesne wykrywanie społecznych zagrożeń i anomalii jest prawdziwym wyzwaniem w dzisiejszch, dynamicznych społeczeństwach. Ludzie tworzą skoplikowane relacje społeczne, które mogą być przedstawione za pomocą różnych typów grafów, których wierzchołki reprezentować mogą aktorów sieci (konkretne osoby lub organizacje) a krawędzie relacje pomiędzy nimi. Analiza tych dynamicznie zmieniających się relacji może wskazywać na niektóre nadciągające...
-
Synchronization helps robots to detect black holes in directed graphs
PublikacjaPraca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano...
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublikacjaPraca dotyczy problemu ścieżek krawędziowo rozłącznych w nieskierowanych grafach pełnych, dla którego podano nowe algorytmy przybliżone: 3.75-przybliżony (model off-line) i 6.47-przybliżony (model on-line). Stosując podobną metodologię, uzyskano algorytm 4.5-przybliżony (off-line) i 6-przybliżony (on-line) dla problemu routingu i kolorowania ścieżek w grafach pełnych.
-
Packing Three-Vertex Paths in 2-Connected Cubic Graphs
PublikacjaW pracy rozważano problem rozmieszczanie ścieżek P3 w 2-spójnych grafach 3-regularnych. Pokazano, że w 2-spójnym grafie 3-regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.
-
Modelling and analysis of beam/bar structure by application of bond graphs
PublikacjaThe paper presents an uniform, port-based approach to modelling of beam/bar systems (trusses). Port-based model of such distributed parameter system has been defined by application of the bond graph methodology and the distributed transfer function method (DTFM). The proposed method of modelling enables to formulate input data for computer analysis by application of the DTFM. The constructed computational package enables the frequency...
-
Experimental evidence about misconception of Terzaghi's 1-D consolidation theory in terms of degree of consolidation
Publikacja -
The Degree of Global DNA Hypomethylation in Peripheral Blood Correlates with That in Matched Tumor Tissues in Several Neoplasia
Publikacja -
Multibeam Echosounder and LiDAR in Process of 360-Degree Numerical Map Production for Restricted Waters with HydroDron
PublikacjaIn order to increase the safety of inland navigation and facilitate the monitoring of the coastal zone of restricted waters, a model of multi-sensory fusion of data from hydroacoustic and optoelectronic systems mounted on the autonomous survey vessel HydroDron will be developed. In the research will be used the LiDAR laser scanner and multibeam echosounder. To increase the visual quality and map accuracy, additionally side scan...
-
Application of Bayesian Networks in risk diagnostics arising from the degree of urban regeneration area degradation
PublikacjaUrban regeneration as a complex project, generates many extremely specific threats affecting the increase of investment risk. Its unique nature causes that probability parameter, normally applied in the process of risk quantification, is extremely difficult to estimate. Due to lack of historical data urban regeneration related activities are therefore associated with uncertainty. According to the authors, a useful tool for resolving...
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublikacjaRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
All graphs with restrained domination number three less than their order
PublikacjaW pracy opisana jest rodzina wszystkich grafów, dla których liczbadominowania zewnętrznego jest o trzy mniejsza od ich rzędu.
-
Efficient List Cost Coloring of Vertices and∕or Edges of Some Sparse Graphs
Publikacja -
Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Publikacja -
Modelling electrical machines using bond graphs for mechatronics system applications.
PublikacjaW artykule przedstawiono modelowanie maszyn elektrycznych metodą grafów wiązań dla potrzeb mechatroniki. Omówiono ogólne założenia modelowania maszyn elektrycznych w ujęciu grafów wiązań, bazującego na modelach wzorcowego sprzężenia transformatorowego i elektromechanicznego. Wykorzystując modele tych sprzężeń przedstawiono w ujęciu grafów wiązań model maszyny indukcyjnej w układzie współrzędnych naturalnych stojana. Model opracowano...
-
Modelling of distributed-lumped parameter systems by application of modal bond graphs.
PublikacjaZastosowano metodę transmitancji układów o parametrach rozłożonych oraz dekompozycję modalną do modelowania wybranych układów dynamicznych. Zaproponowane podejście pozwala otrzymać dokładne modele niskiego rzędu w postaci grafów wiązań.
-
Spam classification methods besed on users e-mail communication graphs
PublikacjaW artykule poddano analizie grafy zbudowane w oparciu o logi serwerów pocztowych. Węzły grafów reprezentują nadawców i odbiorców wiadomości e-mail natomiast krawędzie przedstawiają procesy wymiany wiadomości e-mail. Analiza grafów pozwala na znalezienie korelacji pomiędzy topologią grafów a relacjami pomiędzy użytkownikami serwisu pocztowego. W oparciu o te relacje zaproponowano algorytm klasyfikujący wymieniane wiadomości e-mail...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublikacjaW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaWe consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaIn this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
-
On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
Publikacja -
The effect of the iron oxidation degree on distribution of promotors in the fused catalyst precursors and their activity in the ammonia synthesis reaction
Publikacja -
INFLUENCE OF THE DEGREE OF EJACULATE DILUTION ON THE RESULTS OF THE ASSESSMENT OF MOTILITY OF SPERM OF BREEDING BULLS OBTAINED BY TWO METHODS
Publikacja -
Application of advanced spectroscopic methods in the assessment of the leachability degree of hazardous elements from the matrix of cellular concretea
PublikacjaDue to its structure, autoclaved cellular concrete exhibits good insulating properties with relatively high compressive strength values. It is increasingly used in construction because of its economic attractiveness. Autoclaved cellular concrete is mainly used in interior structure layers, and therefore its potential exposure to heavy metal leaching from the matrix may be related to the presence of a high pH medium from other materials...
-
Multimodal Network Based Graphs of Primitives Storage Concept for Web Mining CBIR
Publikacja -
Derandomizing random walks in undirected graphs using locally fair exploration strategies
PublikacjaW pracy rozważono problem eksploracji anonimowego nieskierowanego grafu przez bezpamięciowego robota. Zaprojektowane strategie eksploracji cechują się własnością lokalnej sprawiedliwości, tj. kolejne krawędzie trawersowane przez robota wybierane są na podstawie lokalnych informacji tak, aby zapewnić równomierne wykorzystanie krawędzi w sensie pewnego kryterium. Okazuje się, że odpowiedni dobór kryterium jest kluczowy do zapewnienia...
-
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....
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Publikacja -
Musical Metadata Retrieval with Flow Graphs, in Rough Sets and Current Trends in Computing.
PublikacjaW pracy opisano metody wyszukiwania muzyki w Internecie w oparciu o opis semantyczny. W eksperymentach wykorzystano opis muzyczny stosowany w bazie CDDB. Zaprezentowano metodę grafów przepływowych zaproponowaną przez Pawlaka.
-
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
PublikacjaWe consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3.
-
How to meet when you forget: log-space rendezvous in arbitrary graphs
PublikacjaProblem rendezvous został dogłębnie zbadany, zarówno dla agendów anonimowych jak i poetykietowanych. zbadano też problem eksploracji grafu za pomocą agentów mobilnych.
-
A note on fast approximate backbone coloring of split graphs with star--like backbones
PublikacjaDla grafu G = (V, E) z wyróżnionym podgrafem H, kolorowanie szkieletowe jest zdefiniowane jako odwzorowanie c spełniające |c(u) - c(v)| > 1 dla każdej krawędzi z E(H) oraz |c(u) - c(v)| > 0 dla każdej krawędzi z E(G). W pracy przedstawiono 1-przybliżony algorytm kolorowania szkieletowego split grafów ze skojarzeniem w szkielecie o złożoności O(|V|) oraz 1-przybliżony algorytm dla split grafów z rozłącznymi gwiazdami w szkielecie.
-
Wind Conditions at Pedestrian Level in Different Types of Residential Urban Development for a High Degree of Land Use Efficiency
PublikacjaThe paper concerns wind conditions around urban building development at the pedestrian level. The article aims to identify aerodynamic phenomena around three types of multi-family housing developmentswith different forms and the same urban parameters of building development intensity (high intensity was taken into account). The aim of the research was mainly to achieve qualitative results that would lead to understanding fundamental...
-
An investigation on the role of GMA grafting degree on the efficiency of PET/PP-g-GMA reactive blending: morphology and mechanical properties
PublikacjaGlycidyl methacrylate (GMA) has been grafted on polypropylene (PP) with the aid of styrene (St) comonomer, by changing dicumyl peroxide initiator content, GMA level, and St concentration. The performance of the resulting PP-g-GMA reactive material towards static and dynamic mechanical properties of poly (ethylene terephthalate) (PET) was monitored in terms of grafting reaction variables and compatibilizer content. Fourier transform...
-
Four Degree-of-Freedom Hydrodynamic Maneuvering Model of a Small Azipod-Actuated Ship With Application to Onboard Decision Support Systems
PublikacjaThe main contribution of this paper is a numerical ship motion model of NTNU’s research vessel Gunnerus, capturing the surge, sway, roll, and yaw dynamics when sailing in uniform and steady currents. The model utilizes a crossflow drag formulation for the transverse viscous loads, and it includes a nonlinear formulation for the propulsion and steering loads provided by two azipod thrusters. A wide range of experimental data obtained...
-
Bond-graphs based modelling of hybrid energy systems with permanent magnet brushless machines
PublikacjaW referacie przedstawiono metodę grafów wiązań (GW) w zastosowaniu do modelowania hybrydowych systemów energetycznych z bezszczotkowymi maszynami elektrycznymi o magnesach trwałych. W części pierwszej referatu omówiono ogólne formalizm GW. Następnie przedstawiono kolejno: ogólną strukturę modelu hybrydowego systemu energetycznego w ujęciu GW; założenia modelowania maszyn elektrycznych w ujęciu GW, model silnika bezszczotkowego...