Elżbieta Sidorowicz

Elżbieta Sidorowicz


Research Focus & Metrics

Academic Career Length

25Years (2002-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2013 in Discussiones Mathematicae Graph Theory
Verified
Journal Article
Open access
KAKinnari Amin
Kinnari Amin
JFJill Faudree
Jill Faudree
RGRonald J. Gould
Ronald J. Gould
ESElżbieta Sidorowicz
Elżbieta Sidorowicz
Discussiones Mathematicae Graph Theory

1 January 2019 in Applicable Analysis and Discrete Mathematics
Verified
Journal Article
Open access
PDF file
MBMieczysław Borowiecki
Mieczysław Borowiecki
AFAnna Fiedorowicz
Anna Fiedorowicz
ESElżbieta Sidorowicz
Elżbieta Sidorowicz
In this paper we introduce a domination game based on the notion of connected domination. Let G = (V,E) be a connected graph of order at least 2. We define a connected domination game on G as follows: The game is played by two players, Dominator and Staller. The players alternate taking turns choosing a vertex of G (Dominator starts). A move of a player by choosing a vertex v is legal, if (1) the vertex v dominates at least one additional vertex that was not dominated by the set of previously chosen vertices and (2) the set of all chosen vertices induces a connected subgraph of G. The game ends when none of the players has a legal move (i.e., G is dominated). The aim of Dominator is to finish as soon as possible, Staller has an opposite aim. Let D be the set of played vertices obtained at the end of the connected domination game (D is a connected dominating set of G). The connected game domination number of G, denoted cg(G), is the minimum cardinality of D, when both players played optimally on G. We provide an upper bound on cg(G) in terms of the connected domination number. We also give a tight upper bound on this parameter for the class of 2-trees. Next, we investigate the Cartesian product of a complete graph and a tree, and we give exact values of the connected game domination number for such a product, when the tree is a path or a star. We also consider some variants of the game, in particular, a Staller-start game.

1 December 2014 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
PDPaul Dorbec
Paul Dorbec
ISIngo Schiermeyer
Ingo Schiermeyer
ESElżbieta Sidorowicz
Elżbieta Sidorowicz
ÉSÉric Sopena
Éric Sopena

1 May 2007 in Information Processing Letters
Verified
Journal Article
Closed access
ESElżbieta Sidorowicz
Elżbieta Sidorowicz

1 January 2012 in Fundamenta Informaticae
Verified
Journal Article
Closed access
PDF file
PBPiotr Borowiecki
Piotr Borowiecki
ESElżbieta Sidorowicz
Elżbieta Sidorowicz
Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm's input during the coloring process. Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problem of dynamic coloring with discoloring constraints for which the performance of the dynamic algorithm Time-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors.

3 January 2007 in The Electronic Journal of Combinatorics
Verified
Journal Article
Closed access
PDF file
MBM. Borowiecki
M. Borowiecki
ESElżbieta Sidorowicz
Elżbieta Sidorowicz
ZTZs. Tuza
Zs. Tuza
We consider the two-player game defined as follows. Let $(G,L)$ be a graph $G$ with a list assignment $L$ on its vertices. The two players, Alice and Bob, play alternately on $G$, Alice having the first move. Alice's goal is to provide an $L$-colouring of $G$ and Bob's goal is to prevent her from doing so. A move consists in choosing an uncoloured vertex $v$ and assigning it a colour from the set $L(v)$. Adjacent vertices of the same colour must not occur. This game will be called game list colouring. The game choice number of $G$, denoted by ch$_g(G)$, is defined as the least $k$ such that Alice has a winning strategy for any $k$-list assignment of $G$. We characterize the class of graphs with ch$_g(G)\le 2$ and determine the game choice number for some classes of graphs.