Search
Filters
total: 93
filtered: 55
-
Catalog
Chosen catalog filters
Search results for: K -PATH VERTEX COVER
-
Some variations of perfect graphs
PublicationWe consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) =γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k -path vertex cover number and the distance (k−1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k≥2. Moreover, we provide a complete characterisation of (ψ2−γ1)-perfect graphs describing the set of its forbidden induced subgraphs and providing...
-
Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
PublicationA vertex cover of a graph G = (V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The ve cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[D]w = (N[D], Ew) weakly induced by D, is connected, where Ew is the set of all edges having at least one vertex in D. The weakly connected domination number γw(G) of G is the minimum cardinality...
-
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,...
-
Parity vertex colouring of graphs
PublicationA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
Dynamic F-free Coloring of Graphs
PublicationA 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...
-
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublicationLet G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...
-
Cops, a fast robber and defensive domination on interval graphs
PublicationThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
On-line ranking of split graphs
PublicationA vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...
-
Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
PublicationWe consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards...
-
2-outer-independent domination in graphs
PublicationWe initiate the study of 2-outer-independent domination in graphs. A 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 at least two neighbors in D, and the set V(G)\D is independent. The 2-outer-independent domination number of a graph G is the minimum cardinality of a 2-outer-independent dominating set of G. We show that if a graph has minimum degree at least two,...
-
An Efficient Noisy Binary Search in Graphs via Median Approximation
PublicationConsider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a strategy, that identifies an initially unknown target vertex in a graph by asking queries. Each query is conducted as follows: the strategy selects a vertex q and receives a reply v: if q is the target, then =, and if q is not the target, then v is a...
-
The convex domination subdivision number of a graph
PublicationLet G = (V;E) be a simple graph. A set D\subset V is a dominating set of G if every vertex in V - D has at least one neighbor in D. The distance d_G(u, v) between two vertices u and v is the length of a shortest (u, v)-path in G. An (u, v)-path of length d_G(u; v) is called an (u, v)-geodesic. A set X\subset V is convex in G if vertices from all (a, b)-geodesics belong to X for any two vertices a, b \in X. A set X is a convex dominating...
-
Preliminary estimation of groundwater recharge on Brda river outwash plain
PublicationEstimation of groundwater recharge is one of the most challenging subjects in hydrogeology. It is a critical factor influencing the pollution migration, assessment of aquifer vulnerability to contamination, small-scale groundwater budget calculation, modeling of nutrient cycling and detailed flow path calculations. In Poland an infiltration rate method is widely used, which depends on a system of rate coefficients referring to...
-
A Framework for Searching in Graphs in the Presence of Errors
PublicationWe consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide...
-
Grade of service determination methodology in IP networks with SIP protocol
PublicationAlthough Grade of Service is very important in VoIP providers evaluation, We wasn't able to find any paper regarding the topic of measuring GoS variables for IP networks utilizing SIP, which are defined like for PSTN/ISDN/GSM networks (post-selection delay, answering delay, release delay, or probability of end-to-end blocking). Due to the lack of research in this field, it was necessary to start from defining measures and cover...
-
Behavior Based Complete Coverage Task of Unknown Area by an Autonomous Mobile Robot SCORPION with Static Obstacles in Environment
PublicationIn the paper the behavior based control system of an autonomous mobile robot SCORPION is presented to execute the one of the most difficult navigation task, which is the complete coverage task of unknown area with static obstacles in the environment. The main principle assumed to design control system was that the robot should cover all area only once, if it possible, to optimize the length of path and energy consumption. All commercial...
-
Society 4.0: Issues, Challenges, Approaches, and Enabling Technologies
PublicationThis guest edition of Cybernetics and Systems is a broadening continuation of our last year edition titled “Intelligence Augmentation and Amplification: Approaches, Tools, and Case Studies”. This time we cover research perspective extending towards what is known as Society 4.0. Bob de Vit brought the concept of Society 4.0 to life in his book “Society 4.0 – resolving eight key issues to build a citizens society”. From the Systems...
-
k-Penalty: A Novel Approach to Find k-Disjoint Paths with Differentiated Path Costs
PublicationW artykule rozpatrywany jest problem ochrony dedykowanej na wypadek awarii wielokrotnej elementów sieci teleinformatycznej. Wspomniana ochrona jest możliwa do zapewnienia poprzez wyznaczenie i zainstalowanie zbioru k rozłącznych ścieżek dla każdego żądania. W szczególności rozpatrywany jest problem wyznaczenia k rozłącznych ścieżek w sieciach typu ''multi-cost'', w przypadku których koszt dowolnego łącza może być różny dla każdej...
-
Comparison and Analysis of Service Selection Algorithms
PublicationIn Service Oriented Architecture, applications are developed by integration of existing services in order to reduce development cost and time. The approach, however, requires algorithms that select appropriate services out of available, alternative ones. The selection process may consider both optimalization requirements, such as maximalization of performance, and constraint requirements, such minimal security or maximum development...
-
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...
-
On extremal sizes of locally k-tree graphs
PublicationA 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...
-
Bounds on the Cover Time of Parallel Rotor Walks
PublicationThe rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in...
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationWe 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.
-
Bounds on the cover time of parallel rotor walks
PublicationThe rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationIn 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 incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.
-
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...
-
The complexity of minimum-length path decompositions
PublicationWe consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...
-
Fast collaborative graph exploration
PublicationWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
Fast Collaborative Graph Exploration
PublicationWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
Fundamental Schemes to Determine Disjoint Paths for Multiple Failure Scenarios
PublicationDisjoint path routing approaches can be used to cope with multiple failure scenarios. This can be achieved using a set of k (k> 2) link- (or node-) disjoint path pairs (in single-cost and multi-cost networks). Alternatively, if Shared Risk Link Groups (SRLGs) information is available, the calculation of an SRLG-disjoint path pair (or of a set of such paths) can protect a connection against the joint failure of the set of links...
-
Finding small-width connected path decompositions in polynomial time
PublicationA connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
Brushing with additional cleaning restrictions
PublicationIn 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...
-
On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn 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...
-
Computational aspects of greedy partitioning of graphs
PublicationIn 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...
-
Fading Characteristics for Dynamic Body-to-Body Channels in Indoor and Outdoor Environments
PublicationThis paper presents an analysis of the fading characteristics in dynamic body-to-body channels, based on measurements performed at 2.45 GHz in indoor and outdoor environments. The statistical analysis of the small- and large-scale fading shows that the Nakagami Distribution is the best model for the former and the Log-Normal one for the latter. An important influence of body shadowing...
-
Path-based methods on categorical structures for conceptual representation of wikipedia articles
PublicationMachine learning algorithms applied to text categorization mostly employ the Bag of Words (BoW) representation to describe the content of the documents. This method has been successfully used in many applications, but it is known to have several limitations. One way of improving text representation is usage of Wikipedia as the lexical knowledge base – an approach that has already shown promising results in many research studies....
-
Clearing directed subgraphs by mobile agents
PublicationWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...
-
Global defensive secure structures
PublicationLet S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we...
-
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
PublicationW 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....
-
Strategic balance in graphs
PublicationFor a given graph G, a nonempty subset S contained in V ( G ) is an alliance iff for each vertex v ∈ S there are at least as many vertices from the closed neighbourhood of v in S as in V ( G ) − S. An alliance is global if it is also a dominating set of G. The alliance partition number of G was defined in Hedetniemi et al. (2004) to be the maximum number of sets in a partition of V ( G ) such that each set is an alliance. Similarly,...
-
Minimum order of graphs with given coloring parameters
PublicationA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
New Tetragonal ReGa5(M) (M = Sn, Pb, Bi) Single Crystals Grown from Delicate Electrons Changing
PublicationSingle crystals of the new Ga-rich phases ReGa~5(Sn), ReGa~5(Pb) and ReGa~5(Bi) were successfully obtained from the flux method. The new tetragonal phases crystallize in the space group P4/mnc (No. 128) with vertex-sharing capped Re2@Ga14 oblong chains. Vacancies were discovered on the Ga4 and Ga5 sites, which can be understood as the direct inclusion of elemental Sn, Pb and Bi into the structure. Heat capacity measurements were...
-
Machine Learning-Based Wetland Vulnerability Assessment in the Sindh Province Ramsar Site Using Remote Sensing Data
PublicationWetlands provide vital ecological and socioeconomic services but face escalating pressures worldwide. This study undertakes an integrated spatiotemporal assessment of the multifaceted vulnerabilities shaping Khinjhir Lake, an ecologically significant wetland ecosystem in Pakistan, using advanced geospatial and machine learning techniques. Multi-temporal optical remote sensing data from 2000 to 2020 was analyzed through spectral...
-
Spatial variability of throughfall in a stand of Scots pine (Pinus sylvestris L.) with deciduous admixture as influenced by canopy cover and stem distance
PublicationVegetation cover affects the amount of precipitation, its chemical composition and its spatial distribution, and this may have implications for the distribution of water, nutrients and contaminants in the subsurface soil layer. The aim of this study was a detailed diagnosis of the spatio-temporal variability in the amount of throughfall (TF) and its chemical components in a 72-year-old pine stand with an admixture of oak and birch....
-
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublicationGiven a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...
-
Dynamic unattended measurement based routing algorithm for diffServ architecture
PublicationDynamic routing is very important in terms of assuring QoS in today's packet networks especially for streaming and elastic services. Existing solutions dedicated to dynamic routing are often too complicated and seem to be not usable in real time traffic scenarios where transferred traffic may vary significantly. This was the main reason for research and new routing mechanism proposal which should apply to today's packet networks....
-
Towards a classification of networks with asymmetric inputs
PublicationCoupled cell systems associated with a coupled cell network are determined by (smooth) vector fields that are consistent with the network structure. Here, we follow the formalisms of Stewart et al (2003 SIAM J. Appl. Dyn. Syst. 2, 609–646), Golubitsky et al (2005 SIAM J. Appl. Dyn. Syst. 4, 78–100) and Field (2004 Dyn. Syst. 19, 217–243). It is known that two non-isomorphic n-cell coupled networks can determine the same sets of...
-
Simulation model for evaluation of QoS routing algorithm in large packet networks
PublicationThe variety of traffic transferred via current telecommunication networks includes also voice, which should meet quality requirements. One of mechanisms, which can support QoS in current packet networks, is routing. There exist many routing proposals which should introduce the QoS into the network but practically they don't. Following paper presents the realization of simulation model for evaluation of a new routing algorithm DUMBRA...