1,721,047 research outputs found
Deciding the winner in k rounds for DISJOINT ARROWS, a new combinatorial partizan game
No full textWe consider DISJOINT ARROWS, a new bounded-length two-player partizan combinatorial game. In this game the two players, Alice and Bob, alternate in choosing vertices on a directed graph and no player is allowed to select a vertex previously selected. At each round Alice selects a vertex u and Bob has to reply choosing a new vertex in the out-neighborhood of u. The first player who cannot move loses. We prove that deciding whether Bob can endure k rounds when k is part of the input is a PSPACE-complete problem. Moreover we prove that the parameterized version of the problem is AW[*]-complete. Thus we provide a new member for the small set of problems known complete for the class AM. (C) 2013 Elsevier B.V. All rights reserved
On the computational complexity of graph closures
No full textThis paper resolves the parallel complexity of the graph closure problem, an open question posed by S. Khuller. In particular, we prove that the 2N - k-closure problem is in L for k = 5 and it is P-complete for k greater than or equal to 6. Finally, we show that the N + k-closure problem is P-complete for any integer k
Effects of graph operations on star pairwise compatibility graphs
Full text linkA graph
is defined as a star-
-pairwise compatibility graph (PCG) when it is possible to assign a positive real number weight
to each vertex
, and define
distinct intervals
, in such a way that there is an edge
in
if and only if the sum of the weights of vertices
and
falls within the union of these intervals. The star-
-PCG class is connected to two significant graph categories: PCGs and multithreshold graphs. The star number of a graph
, is the smallest
for which
is a star-
-PCG. In this paper, we study the effects of various graph operations, such as the addition of twins, pendant vertices, universal vertices, or isolated vertices, on the star number of the graph resulting from these operations. As significant applications of our findings, we determine the star number of lobster graphs and provide an upper bound for the star number of acyclic graphs. This is particularly interesting as determining the star number is notoriously difficult and is known only for a few classes of graphs. Indeed, for acyclic graphs, the exact value of the star number is currently known only for caterpillars [1]
Compact representations of the intersection structure of families of finite sets
No full textThe Nešetřil-Pultr dimension of the Kneser graph is interpreted as the shortest length of strings over an infinite alphabet representing the vertices of the graph so that the absence of coincidences in the codewords of a pair of vertices is equivalent to adjacency, i.e., to the two underlying sets being disjoint. We study analogous but more demanding representations in case the alphabet size may be limited and yet the full intersection has to be determined from the coincidences. Our results introduce a connection between extremal set theory and zero-error problems in multiterminal source coding in the Shannon sense
- …
