In this article, we propose a method to identify the link layer home network topology, motivated by applications to cost reduction of support centers. If the topology of home networks can be identified automatically and efficiently, it is easier for operators of support centers to identify fault points. We use MAC address forwarding tables (AFTs) which can be collected from network devices. There are a couple of existing methods for identifying a network topology using AFTs, but they are insufficient for our purpose; they are not applicable to some specific network topologies that are typical in home networks. The advantage of our method is that it can handle such topologies. We also implemented these three methods and compared their running times. The result showed that, despite its wide applicability, our method is the fastest among the three.

In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.

This paper introduces a new timetabling problem on universities, called interview timetabling. In this problem, some constant number, say three, of referees are assigned to each of 2n graduate students. Our task is to construct a presentation timetable of these 2n students using n timeslots and two rooms, so that two students evaluated by the same referee must be assigned to different timeslots. The optimization goal is to minimize the total number of movements of all referees between two rooms. This problem comes from the real world in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexities.

The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered.In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop (LQD) policy is (4M-4)/(3M-2) in the case of N=2, where N is the number of output ports in a switch and M is the size of the buffer.This matches the lower bound given by Hahne, Kesselman and Mansour.Also, in the case of arbitrary N, we improve the competitive ratio of LQD from 2 to 2 - (1/M) minK = 1, 2, ..., N{M/K + K - 1}.

An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio for an arbitrarily positive constant c, where N denotes the number of men in an input.

The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. In this paper, we consider one of the most standard models, called multi-queue switches model. In this model, Albers et al. gave a lower bound , and Azar et al. gave an upper bound on the competitive ratio when m, the number of input ports, is large. They are tight, but there still remains a gap for small m. In this paper, we consider the case where m=2, namely, a switch is equipped with two ports, which is called a bicordal buffer model. We propose an online algorithm called Segmental Greedy Algorithm (SG) and show that its competitive ratio is at most ( 1.231), improving the previous upper bound by ( 1.286). This matches the lower bound given by Schmidt.

The purpose of the online graph exploration problem is to visit all the nodes of a given graph and come back to the starting node with the minimum total traverse cost. However, unlike the classical Traveling Salesperson Problem, information of the graph is given online. When an online algorithm (called a searcher) visits a node v, then it learns information on nodes and edges adjacent to v. The searcher must decide which node to visit next depending on partial and incomplete information of the graph that it has gained in its searching process. The goodness of the algorithm is evaluated by the competitive analysis. If input graphs to be explored are restricted to trees, the depth-first search always returns an optimal tour. However, if graphs have cycles, the problem is non-trivial. In this paper we consider two simple cases. First, we treat the problem on simple cycles. Recently, Asahiro et al. proved that there is a 1.5-competitive online algorithm, while no online algorithm can be (1.25-ε)-competitive for any positive constant ε. In this paper, we give an optimal online algorithm for this problem; namely, we give a (1.366)-competitive algorithm, and prove that there is no (-ε)-competitive algorithm for any positive constant ε. Furthermore, we consider the problem on unweighted graphs. We also give an optimal result; namely we give a 2-competitive algorithm and prove that there is no (2-ε)-competitive online algorithm for any positive constant ε.