Browsing by Author "Mujuni, Egbert"

Now showing 1 - 8 of 8
  • Thumbnail Image
    Item
    Covering Graphs with Few Complete Bipartite Subgraphs
    (Elsevier, 2009) Fleischner, Herbert; Mujuni, Egbert; Paulusma, Daniël; Szeider, Stefan
    We consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the biclique partition problem is defined similarly with the additional condition that the bicliques are required to be mutually edge-disjoint. The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most k bicliques, the biclique vertex-partition problem is defined similarly with the additional condition that the bicliques are required to be mutually vertex-disjoint. All these four problems are known to be NP-complete even if the given graph is bipartite. In this paper, we investigate them in the framework of parameterized complexity: do the problems become easier if k is assumed to be small? We show that, considering k as the parameter, the first two problems are fixed-parameter tractable, while the latter two problems are not fixed-parameter tractable unless P=NP.
  • Thumbnail Image
    Item
    An Examination Scheduling Algorithm Using Graph Colouring
    (International Journal of Computer Engineering & Applications, 2013-04) Mohamed, Selemani; Mujuni, Egbert; Mushi, Allen
    This paper presents a graph coloring based algorithm for Examinations Timetabling Problem at Sokoine University of Agriculture (SUA) in Tanzania. A Recursive Largest First algorithm for graph coloring is applied to find timeslots. We present a summary of results which indicates good performance
  • Thumbnail Image
    Item
    A Hybrid Weighted Periodical Pattern Mining and Prediction for Personal Mobile Commerce
    (Academic Journals, 2013) Preetha, D.; Mythili, K.; Karthika, D.; RangaRaj, R.; Priya, P. H.; Amuthajanaki, B.; Jayalakshmi, K.; Kahebo, M.; Mujuni, Egbert; Mushi, A.
    In case of large amount of the search engine based applications, mobile e-commerce has established a more interest under both industry and academia. From that mining the user behavior and prediction of the user to analysis the mobile commerce behaviors based on their actions are most important. To perform these steps, previous work proposed a novel structure called Mobile Commerce Explorer (MCE). It can be performed in three ways 1) Similarity Inference Model (SIM) for measuring the similarities amongst stores and items 2) Personal Mobile Commerce Pattern Mine (PMCP-Mine) algorithm for well-organized discovery of mobile users Personal Mobile Commerce Patterns (PMCPs); and 3) Mobile Commerce Behavior Predictor (MCBP) for prediction of possible mobile user behaviors. Assigning the weight values for each item in the mobile transaction database finds the best frequent pattern mining from the mobile user pattern .Proposed system considering the different weight values for each item and the select the best weight values to frequent pattern mining .Selection of best weight values from the different weight values we use particle swarm optimization algorithm system is initialized with a population of random solution such as different weight values and search for best weight values by updating invention. The particle swarm optimization changing the velocity of each particle toward finds best weight values at both local and global locations. After finding the weight values than derive the frequent pattern mining results from the existing transaction behavior of each mobile users .Weighted frequent pattern mining with PSO achieve an wide-ranging investigational estimation by replication and show that better accuracy outcome.
  • Thumbnail Image
    Item
    Mathematical Formulation Model for a School Bus Routing Problem with Small Instance Data
    (2014) Manumbu, Denis M.; Mujuni, Egbert; Kuznetsov, Dmitry
    This paper aims to describe the mathematical formulation model and an exact optimal solution analyses for a school bus routing problem with small instance data. The formulated model has been used to compute the optimal solution of time spent by students at all bus stops, apart from that the bus stops are not necessary be linearly ordered. We also listed down five procedures of mathematical formulation model to reach an exact optimal solution for a school bus routing problem with small instance data. We assume that each bus has fixed pick up points, these generates the many possible routes for a bus, the number of routes that generated is equal to permutation of pick up points, for each route of a bus we computing the objective function and the route with smallest objective function value can be optimal route of a bus. The sample data from two schools located at Dar es Salaam are collected and validated in the model to shows the good performing of that model. The optimal solution results obtained shows that the students spent minimal minutes in new planned routes compared to current routes.
  • Thumbnail Image
    Item
    Optimizing Schedules for School Bus Routing Problem: the case of Dar Es Salaam Schools
    (International Journal of Advanced Research in Computer Science, 2015-02) Ngonyani, Beatha; Mujuni, Egbert; Mushi, Allen
    The School Bus Routing Problem (SBRP) deals with transportation of students to and from their schools. Given a set of fleet of buses of a school, a set of bus stops, the time matrix and the number of students at each stop, the task is to determine the schedule of buses that minimizes amount of time students spend in the buses on the way to and from school. The school bus routing problem is a special case of the Vehicle Routing Problem (VRP) and is known to be NP-hard. This NP-hardness implies that it is very unlikely that the problem can be solved in polynomial time. The common methods used to solve NP-hard problems are heuristic algorithms which gives quick and good solutions without guarantee that the solution obtained is optimal. In this paper a Tabu search based heuristic for SBRP is developed. The algorithm has been implemented using Borland C++ 4.5 programming language and tested using data from Tusiime Nursery and Primary School in Dar es salaam, Tanzania. The proposed implementation results in reduction of students’ travelling time by 19.24%.
  • Thumbnail Image
    Item
    Parameterized Algorithms in Smooth 4-Regular Hamiltonian Graphs
    (Springer, 2008) Mujuni, Egbert
    Smooth 4-regular hamiltonian graphs are generalizations of cycle plus triangles graphs. It has been shown that both the independent set and 3-colorability problems are NP-Complete in this class of graphs. In this paper we show that these problems are fixed parameter tractable if we choose the number of inner cycles as parameter.
  • Thumbnail Image
    Item
    Parameterized Complexity of the Clique Partition Problem
    (2008) Mujuni, Egbert; Rosamond, Frances
    The problem of deciding whether the edge-set of a given graph can be partitioned into at most k cliques is well known to be NP-complete. In this paper we investigate this problem from the point of view of parameterized complexity. We show that this problem is fixed parameter tractable if we choose the number of cliques as parameter. In particular, we show that in polynomial time, a kernel bounded by k 2 can be obtained, where k is the number of cliques. We also give an O(2((k+3) log k)/2n) algorithm for this problem in K4-free graphs.
  • Thumbnail Image
    Item
    Solving the Examination Timetabling Problem Using a Two-Phase Heuristic
    (2015) Mujuni, Egbert; Mushi, Allen
    Examination timetabling is an important operational problem in any academic institution. The problem involves assigning examinations and candidates to time periods and examination rooms while satisfying a set of specific constraints. An increased number of student enrolments, a wider variety of courses, and the growing flexibility of students’ curricula have contributed to the growing challenge in preparing examination timetables. Since examination timetabling problems differ from one institution to another, in this paper we develop and investigate the impact of a two-phase heuristic that combines Graph-Colouring and Simulated Annealing at Sokoine University of Agriculture (SUA) in Tanzania. Computational results are presented which shows great improvement over the previous work on the same problem.