Hanna Furmańczyk

Hanna Furmańczyk

Auto-generated profile, based on publicly available information

Hanna Furmańczyk


Research Focus & Metrics

Academic Career Length

19Years (2008-Present)

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

Representative Publications

View All Publications
1 January 2018 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
HFHanna Furmańczyk
Hanna Furmańczyk
MKMarek Kubale
Marek Kubale

1 September 2016 in Archives of Control Sciences
Verified
Journal Article
Open access
PDF file
HFHanna Furmańczyk
Hanna Furmańczyk
AJAndrzej Jastrzębski
Andrzej Jastrzębski
MKMarek Kubale
Marek Kubale
In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs

1 February 2017 in Bulletin Of The Polish Academy Of Sciences-Technical Sciences
Verified
Journal Article
Open access
PDF file
HFH. Furmańczyk
H. Furmańczyk
MKM. Kubale
M. Kubale
In the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s1 ≥ s2 ≥ s3 ≥ s4, respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Δ, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s1 = s2 = s3. If, however, Δ ≤ 4 and s1 ≥ 12s2, s2 = s3 = s4, then the problem can be solved to optimality in time O(n1.5). The same algorithm returns a solution of value at most 2 times optimal provided that s1 ≥ 2s2. Finally, we study the case s1 ≥ s2 ≥ s3 = s4 and give a 32/15-approximation algorithm running also in O(n1.5) time.

5 February 2016 in Ars Mathematica Contemporanea
Verified
Journal Article
Closed access
HFHanna Furmanczyk
Hanna Furmanczyk
MKMarek Kubale
Marek Kubale
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 and it is denoted by χ = (G). In this paper the problem of determinig χ =  for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas of cubic graphs is solvable in polynomial time, the problem of equitable coloring becomes NP-hard for these graphs. We provide polynomially solvable cases of coronas of cubic graphs and prove the NP-hardness in a general case. As a by-product we obtain a simple linear time algorithm for equitable coloring of such graphs which uses χ = (G) or χ = (G) + 1 colors. Our algorithm is best possible, unless P=NP. Consequently, cubical coronas seem to be the only known class of graphs for which equitable coloring is harder than ordinary coloring.

1 March 2015 in Archives of Control Sciences
Verified
Journal Article
Open access
HFHanna Furmańczyk
Hanna Furmańczyk
MKMarek Kubale
Marek Kubale
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 the makespan

16 May 2008 in Information Processing Letters
Verified
Journal Article
Closed access
HFHanna Furmańczyk
Hanna Furmańczyk
AKAdrian Kosowski
Adrian Kosowski
PŻPaweł Żyliński
Paweł Żyliński