Researcher profile

Didem Gözüpek

Didem Gözüpek contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Data Structures and Algorithms Computational Complexity Networking and Internet Architecture

Trust snapshot

Quick read

Trust 15 - Baseline

3works

0followers

3topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Edge Coloring with Minimum Reload/Changeover Costs

In an edge-colored graph, a traversal cost occurs at a vertex along a path when consecutive edges with different colors are traversed. The value of the traversal cost depends only on the colors of the traversed edges. This concept leads to two global cost measures, namely the \emph{reload cost} and the \emph{changeover cost}, that have been studied in the literature and have various applications in telecommunications, transportation networks, and energy distribution networks. Previous work focused on problems with an edge-colored graph being part of the input. In this paper, we formulate and focus on two pairs of problems that aim to find an edge coloring of a graph so as to minimize the reload and changeover costs. The first pair of problems aims to find a proper edge coloring so that the reload/changeover cost of a set of paths is minimized. The second pair of problems aim to find a proper edge coloring and a spanning tree so that the reload/changeover cost is minimized. We present several hardness results as well as polynomial-time solvable special cases.

preprint2016arXiv

Parameterized complexity of the MINCCA problem on graphs of bounded decomposability

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The "Minimum Changeover Cost Arborescence" (MINCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gözüpek et al. [TCS 2016] that the problem is FPT when parameterized by the treewidth and the maximum degree of the input graph. In this article we present the following results for the MINCCA problem: - the problem is W[1]-hard parameterized by the treedepth of the input graph, even on graphs of average degree at most 8. In particular, it is W[1]-hard parameterized by the treewidth of the input graph, which answers the main open problem of Gözüpek et al. [TCS 2016]; - it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph; - it is FPT parameterized by the star tree-cutwidth of the input graph, which is a slightly restricted version of tree-cutwidth. This result strictly generalizes the FPT result given in Gözüpek et al. [TCS 2016]; - it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs.

preprint2013arXiv

A Fair Scheduling Model for Centralized Cognitive Radio Networks

We formulate throughput maximizing, max-min fair, weighted max-min fair, and proportionally fair scheduling problems for cognitive radio networks managed by a centralized cognitive base station. We propose a very general scheduling model accomplishing goals such as making frequency, time slot, and data rate allocation to secondary users with possibly multiple antennas, in a heterogenous multi-channel and multi-user scenario. Moreover, our schedulers ensure that reliable communication between the cognitive base station and secondary users are maintained, no collisions occur among secondary users, and primary users in the service area of the cognitive base station are not disturbed. Two distinctive features of our fair schedulers are that they provide joint temporal and throughput fairness, and take throughput values experienced by secondary users in the recent past, referred to as window size, into account and use this information in the current scheduling decision. We also propose a heuristic algorithm for our fair schedulers and demonstrate through simulations that our proposed heuristic yields very close solutions to the values obtained from the optimization softwares. Furthermore, we make extensive simulations to evaluate our schedulers' performance in terms of both total throughput and fairness for varying number of secondary users, frequencies, antennas, and window size.