Wyniki wyszukiwania dla: CUBIC GRAPH - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: CUBIC GRAPH

Wyniki wyszukiwania dla: CUBIC GRAPH

  • On bipartization of cubic graphs by removal of an independent set

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - 2016

    We study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.

    Pełny tekst w serwisie zewnętrznym

  • Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring

    A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...

    Pełny tekst w serwisie zewnętrznym

  • Total Domination Versus Domination in Cubic Graphs

    A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...

    Pełny tekst w portalu

  • Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

    In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize...

    Pełny tekst w serwisie zewnętrznym

  • Tighter bounds on the size of a maximum P3-matching in a cubic graph

    Publikacja

    W pracy pokazano, że największe P3-skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.

    Pełny tekst w serwisie zewnętrznym

  • Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs

    Publikacja

    - 2016

    In 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.

    Pełny tekst w serwisie zewnętrznym

  • Packing Three-Vertex Paths in 2-Connected Cubic Graphs

    Publikacja

    - ARS COMBINATORIA - 2008

    W 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.

    Pełny tekst w serwisie zewnętrznym

  • Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - 2018

    We 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.

    Pełny tekst w serwisie zewnętrznym

  • Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - 2018

    We 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.

  • Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

    Publikacja

    - Archives of Control Sciences - 2015

    Pełny tekst w serwisie zewnętrznym

  • Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych

    Publikacja

    - 2014

    W pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NP-zupełny w szerokim zakresie parametrów grafów.

  • Marek Kubale prof. dr hab. inż.

     Details concerning: Qualifications, Experiences, Editorial boards, Ph.D. theses supervised, Books, and Recent articles can be found at http://eti.pg.edu.pl/katedra-algorytmow-i-modelowania-systemow/Marek_KubaleGoogle ScholarSylwetka prof. Marka Kubalego Prof. Marek Kubale pracuje na Wydziale ETI Politechniki Gdańskiej nieprzerwanie od roku 1969. W tym czasie napisał ponad 150 prac naukowych, w tym ponad 40 z listy JCR. Ponadto...

  • Discussiones Mathematicae Graph Theory

    Czasopisma
    SHERPA RoMEO Szary Pomoc

    ISSN: 1234-3099

  • Joanna Raczek dr inż.

    Wykształcenie 1997 -- 2001 Studia inżynierskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2001 -- 2003 Studia magisterskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2000 -- 2004 Studia inżynierskie, Wydział Elektroniki, Informatyki i...

  • Modelling of Curvature of the Railway Track Geometrical Layout Using Particle Swarm Optimization

    A method of railway track geometrical layout design, based on application of cubic C-Bezier curves for describing the layout curvature is presented in the article. The control points of a cubic C-Bezier curve are obtained in an optimization process carried out using Particle Swarm Optimization algorithm. The optimization criteria are based on the evaluation of the dynamic interactions and satisfaction of geometrical design requirements.

  • Krzysztof Goczyła prof. dr hab. inż.

    Krzysztof Goczyła, profesor zwyczajny Politechniki Gdańskiej, informatyk, specjalista z inżynierii oprogramowania, inżynierii wiedzy i baz danych. Ukończył studia wyższe na  Wydziale Elektroniki Politechniki Gdańskiej w 1976 r. jako magister inżynier elektronik w specjalności automatyka. Na Politechnice Gdańskiej pracuje od 1976. Na Wydziale Elektroniki PG w 1982 r. uzyskał doktorat z informatyki, a w 1999 r. habilitację. W 2012...

  • EvOLAP Graph – Evolution and OLAP-Aware Graph Data Model

    Publikacja

    - 2018

    The objective of this paper is to propose a graph model that would be suitable for providing OLAP features on graph databases. The included features allow for a multidimensional and multilevel view on data and support analytical queries on operational and historical graph data. In contrast to many existing approaches tailored for static graphs, the paper addresses the issue for the changing graph schema. The model, named Evolution...

    Pełny tekst w serwisie zewnętrznym

  • Synergic Effect of Naphthylated Carbon Nanotubes and Gold Nanoparticles on Catalytic Performance of Hybrid Films Containing Bilirubin Oxidase for the Dioxygen Reduction

    Publikacja

    - ELECTROANALYSIS - 2017

    To improve the direct electron transfer from a multicopper oxidase MvBOd to the glassy carbon electrode surface the naphthylated multiwall carbon nanotubes (Napht-MWCNTs) are ombined with gold nanoparticles (AuNPs) to form a conductive network at the electrode and to increase its working surface. Such approach allowed to eliminate the necessity of employing mediators to reach elevated current values. The enzyme stability was improved...

  • Constructing a map of an anonymous graph: applications of universal sequences

    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - 2010

    We study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...

    Pełny tekst w serwisie zewnętrznym

  • Equitable coloring of corona multiproducts of graphs

    Publikacja

    - Discussiones Mathematicae Graph Theory - 2017

    We give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.

  • Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs

    Publikacja

    - 2011

    In 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...

    Pełny tekst w serwisie zewnętrznym

  • Dynamic F-free Coloring of Graphs

    Publikacja

    - GRAPHS AND COMBINATORICS - 2018

    A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...

    Pełny tekst w serwisie zewnętrznym

  • Colorings of the Strong Product of Circulant Graphs

    Publikacja
    • M. Jurkiewicz

    - 2012

    Graph coloring is one of the famous problems in graph theory and it has many applications to information theory. In the paper we present colorings of the strong product of several circulant graphs.

  • On trees with double domination number equal to total domination number plus one

    Publikacja

    A 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. A vertex of a graph is said to dominate itself and all of its neighbors. A double 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. The total (double, respectively) domination number of a graph G is the minimum cardinality of a total (double,...

    Pełny tekst w serwisie zewnętrznym

  • Workshop on Graph Theory

    Wydarzenia

    01-07-2019 00:00 - 05-07-2019 23:59 http://gwgt.mif.pg.gda.pl Nauka

    The Gdańsk Workshop on Graph Theory (GWGT) is an annual, informal workshop whose goal is to provide a forum for scientists to meet, present their work, interact, and establish collaborations in the field of Graph Theory

  • Nordhaus-Gaddum results for the convex domination number of a graph

    Publikacja

    - Periodica Mathematica Hungarica - 2012

    Praca dotyczy nierówności typu Nordhausa-Gadduma dla dominowania wypukłego.

    Pełny tekst w serwisie zewnętrznym

  • Zgred - Zgred Graph Editor

    Publikacja

    The paper presents a graph editor that was developed as a supplementary tool for the Koala graph library. We discuss its requirements, design choices and main ideas behind the implementation. The later part of the paper is meant to be a brief user manual, as we go through the functionality provided by the editor

  • Linear game non-contextuality and Bell inequalities—a graph-theoretic approach

    Publikacja

    - NEW JOURNAL OF PHYSICS - 2016

    We study the classical and quantum values of a class of one-and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR(XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the...

    Pełny tekst w serwisie zewnętrznym

  • Solving Boundary Value Problems for Second Order Singularly Perturbed Delay Differential Equations by ε-Approximate Fixed-Point Method

    Publikacja

    In this paper, the boundary value problem for second order singularly perturbed delay differential equation is reduced to a fixed-point problem v = Av with a properly chosen (generally nonlinear) operator A. The unknown fixed-point v is approximated by cubic spline vh defined by its values vi = vh(ti) at grid points ti, i = 0, 1, ... ,N. The necessary for construction the cubic spline and missing the first derivatives at the boundary...

    Pełny tekst w serwisie zewnętrznym

  • The electronic characterization of the cubic Laves-phase superconductor CaRh2

    We present the synthesis and experimental characterization of the electronic properties of the cubic Laves phase superconductor CaRh2. Its crystal structure was confirmed by powder X-ray diffraction and its ambient temperature lattice parameter (a = 7.5326(6) Å) is in good agreement with the literature. Magnetization, resistivity and heat-capacity measurements indicate that CaRh2 is a moderate-coupling type-II superconductor (λe-p = 0.89)...

    Pełny tekst w serwisie zewnętrznym

  • Equitable coloring of corona products of graphs

    Publikacja
    • H. Furmańczyk
    • K. Kaliraj
    • M. Kubale
    • J. Vernold Vivin

    - Advances and Applications in Discrete Mathematics - 2013

    In this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NP-complete even if G is 4-regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.

    Pełny tekst w serwisie zewnętrznym

  • On extremal sizes of locally k-tree graphs

    Publikacja

    - CZECHOSLOVAK MATHEMATICAL JOURNAL - 2010

    A 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...

    Pełny tekst w serwisie zewnętrznym

  • The accretion of the new ice layer on the surface of hexagonal ice crystal and the influence of the local electric field on this process

    The process of creation of a new layer of ice on the basal plane and on the prism plane of a hexagonal ice crystal is analyzed. It is demonstrated that the ordering of water molecules in the already existing crystal affects the freezing. On the basal plane, when the orientations of water molecules in the ice block are random, the arrangement of the new layer in a cubic manner is observed more frequently — approximately 1.7 times...

    Pełny tekst w portalu

  • On Computational Aspects of Greedy Partitioning of Graphs

    Publikacja

    - 2017

    In this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...

    Pełny tekst w serwisie zewnętrznym

  • On Tradeoffs Between Width- and Fill-like Graph Parameters

    In this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1,...

    Pełny tekst w serwisie zewnętrznym

  • Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks

    Publikacja

    - 2014

    We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal...

    Pełny tekst w serwisie zewnętrznym

  • Rendezvous of heterogeneous mobile agents in edge-weighted networks

    We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal...

    Pełny tekst w serwisie zewnętrznym

  • Brushing with additional cleaning restrictions

    In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. We consider the process where at each time step, a vertex that has at least as many brushes as incident, contaminated edges, sends brushes down these edges to clean them. Various problems arise, such as determining the minimum number of brushes (called the brush number) that are required to clean the entire graph. Here, we study a new variant...

    Pełny tekst w serwisie zewnętrznym

  • Computational aspects of greedy partitioning of graphs

    In this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...

    Pełny tekst w serwisie zewnętrznym

  • Hat problem on a graph

    Publikacja

    The topic of our paper is the hat problem. In that problem, each of n people is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color looking at the hat colors of the other people. The team wins if at least one person guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of win. In this version every...

    Pełny tekst w serwisie zewnętrznym

  • On the hat problem on a graph

    Publikacja

    The topic of this paper is the hat problem in which each of n players is uniformly and independently fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning....

    Pełny tekst w serwisie zewnętrznym

  • Graph security testing

    Set S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs...

    Pełny tekst w serwisie zewnętrznym

  • Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs

    Publikacja

    - 2014

    We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size...

    Pełny tekst w serwisie zewnętrznym

  • Leader election for anonymous asynchronous agents in arbitrary networks

    Publikacja

    We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph...

    Pełny tekst w serwisie zewnętrznym

  • Application of genetic algorithms in graph searching problem

    Graph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called...

  • On trees with double domination number equal to 2-outer-independent domination number plus one

    A vertex of a graph is said to dominate itself and all of its neighbors. A double 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. The double domination number of a graph G is the minimum cardinality of a double dominating set of G. For a graph G=(V,E), a subset D subseteq V(G) is a 2-dominating set if every vertex of V(G)D has at least two neighbors...

    Pełny tekst w serwisie zewnętrznym

  • Interpolation properties of domination parameters of a graph

    An integer-valued graph function π is an interpolating function if a set π(T(G))={π(T): T∈TT(G)} consists of consecutive integers, where TT(G) is the set of all spanning trees of a connected graph G. We consider the interpolation properties of domination related parameters.

    Pełny tekst w serwisie zewnętrznym

  • Three-fast-searchable graphs

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - 2013

    In the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...

    Pełny tekst w serwisie zewnętrznym

  • An Alternative Proof of a Lower Bound on the 2-Domination Number of a Tree

    Publikacja

    A 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...

    Pełny tekst w serwisie zewnętrznym

  • Modeling the impact of surface currents in a harbor using graph theory

    Publikacja
    • J. Pyrchla
    • L. Kasyk
    • M. Leyk
    • M. Kijewska
    • M. Kowalewski

    - Zeszyty Naukowe / Akademia Morska w Szczecinie - 2016

    Ensuring security in a harbor requires research into its infrastructure using spatial environmental data. This paper presents a methodology that defines the design of a graph for modeling the interactions between surface currents and moving objects. Combining this graph with port charts that integrate electronic navigation charts with coastal orthophotographs allows us to perform a multidimensional analysis. In addition, the complete...

    Pełny tekst w serwisie zewnętrznym