| IEICE Technical Committee Submission System Conference Schedule |
Online Proceedings [Sign in] Tech. Rep. Archives |
Technical Committee on Theoretical Foundations of Computing (COMP) (Searched in: 2013)
Search Results: Keywords 'from:2013-12-20 to:2013-12-20'
| Committee | Date Time | Place | Paper Title / Authors | Abstract | Paper # | |
| COMP | 2013-12-20 09:30 |
Okinawa | Okinawa Industry Support Center | Reflections on a CFL decision problem "L(G)=Σ* ?" Eiiichi Tanaka  COMP2013-38 |
The decision problem "whether a context free grammar G generates all terminal strings or not" has been considered to be ... [more] | COMP2013-38 pp.1-6 |
| COMP | 2013-12-20 09:55 |
Okinawa | Okinawa Industry Support Center | Algorithms for Independent Set Reconfiguration Problem on Graphs Erik D. Demaine, Martin L. Demaine (Massachusetts Inst. of Tech.), Takehiro Ito (Tohoku Univ.), Hirotaka Ono (Kyushu Univ.), Ryuhei Uehara (JAIST) COMP2013-39 |
Suppose that we are given two independent sets Ib and Ir of a graph such that |Ibj| = |Ir|, and imagine that a token is ... [more] | COMP2013-39 pp.7-14 |
| COMP | 2013-12-20 10:20 |
Okinawa | Okinawa Industry Support Center | On Enumerating All Maximal Cliques in Unit Disk Graphs Daisuke Suzuki, Taisuke Izumi (Nagoya Inst. of Tech.) COMP2013-40 |
This paper considers the problem of enumerating all maximal cliques in unit disk graphs, which is a plausible setting fo... [more] | COMP2013-40 pp.15-20 |
| COMP | 2013-12-20 11:00 |
Okinawa | Okinawa Industry Support Center | Localization of eigenvector centrality on single-defect networks Hiroki Yamaguchi (Tokyo Inst. of Tech.) COMP2013-41 |
We proved that positive eigenvectors of almost all single-defect graphs, each of them consists of vertices having unif... [more] |
COMP2013-41 pp.21-26 |
| COMP | 2013-12-20 11:25 |
Okinawa | Okinawa Industry Support Center | An empirical study for independent distance dominating sets in large-scale graphs Hiroshi Kadowaki, Liang Zhao (Kyoto Univ.), Dorothea Wagner (Karlsruhe Inst. of Tech.) COMP2013-42 |
This paper studies the scaling behavior of the size of a minimum independent distance dominating set (MIDDS) in large-sc... [more] | COMP2013-42 pp.27-31 |
| COMP | 2013-12-20 13:20 |
Okinawa | Okinawa Industry Support Center | On the Extension of the Serial Dictatorship with Project Closures Naoyuki Kamiyama (Kyushu Univ.) COMP2013-43 |
[more] | COMP2013-43 pp.33-37 |
| COMP | 2013-12-20 13:45 |
Okinawa | Okinawa Industry Support Center | A Power Allocation Management System Using an Algorithm for the Knapsack Problem Naoyuki Morimoto, Yuu Fujita, Masaaki Yoshida, Hiroyuki Yoshimizu, Masafumi Takiyamada, Terukazu Akehi, Masami Tanaka (Enegate) COMP2013-44 |
Power management for saving energy and reducing peak load can be viewed as the knapsack problem as follows; an appliance... [more] | COMP2013-44 pp.39-43 |
| COMP | 2013-12-20 14:25 |
Okinawa | Okinawa Industry Support Center | The Hidden K-matrix Linear Complementarity Problem is at Least as Hard as Linear Programming over Cubes Jan Foniok (Univ. of Warwick), Komei Fukuda (ETH Zurich), Lorenz Klaus (NII/JST) COMP2013-45 |
The linear complementarity problem (LCP) is a framework that unifies optimization problems, such as linear programming, ... [more] | COMP2013-45 pp.45-52 |
| COMP | 2013-12-20 14:50 |
Okinawa | Okinawa Industry Support Center | Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions Hiroki Morizumi (Shimane Univ.) COMP2013-46 |
Sensitivity, block sensitivity, and certificate complexity are complexity measures for Boolean functions. In this note, ... [more] | COMP2013-46 pp.53-55 |
| COMP | 2013-12-20 15:30 |
Okinawa | Okinawa Industry Support Center | [Tutorial Lecture]
Introduction to Computational Complexity Theory (5): Approaches to P vs. NP via Circuits Kazuhisa Seto (Seikei Univ.) COMP2013-47 |
In this talk, we give a brief introduction to Circuit Complexity and Circuit Satisfiability Problems. At first, we prov... [more] | COMP2013-47 p.57 |
| COMP | 2013-12-21 09:30 |
Okinawa | Okinawa Industry Support Center | An Adjustable Work Space Algorithm for Finding a Shortest Path in a Simple Polygon Matsuo Konagaya, Tetsuo Asano (JAIST), Otfried Cheong (KAIST), Sang Won Bae (Kyonggi Univ.) COMP2013-48 |
Given a simple polygon with $n$ vertices in a plane, we compute the shortest path between two query points using less ... [more] |
COMP2013-48 pp.59-62 |
| COMP | 2013-12-21 09:55 |
Okinawa | Okinawa Industry Support Center | An Algorithm for Finding the Point Minimizing the Distance Error to Given Points Shigeki Nakamura, Tetsuo Asano (JAIST), Siu-Wing Cheng (HKUST) COMP2013-49 |
Given $n$ points in the plane, we want to insert a new point in the distance specified by the input from each existing p... [more] | COMP2013-49 pp.63-68 |
| COMP | 2013-12-21 10:20 |
Okinawa | Okinawa Industry Support Center | Adjustable Work Space Algorithm of Arrangement of Lines Takahiro Seii, Tetsuo Asano (JAIST) COMP2013-50 |
This paper presents an adjustable work space algorithm for an arrangement of lines. An arrangement of lines is the part... [more] |
COMP2013-50 pp.69-72 |
| COMP | 2013-12-21 11:00 |
Okinawa | Okinawa Industry Support Center | Sublinear-time cake-cutting algorithms Takahiro Ueda (Kyoto Univ.), Hiro Ito (Univ. of Electro-Comm.) COMP2013-51 |
In this research, we show sub-linear time algorithms for the cake-cutting problem. The cake-cutting problem is a problem... [more] | COMP2013-51 pp.73-79 |
| COMP | 2013-12-21 11:25 |
Okinawa | Okinawa Industry Support Center | Efficient Algorithms for Sorting $k$-Sets in Bins Kazuhisa Seto (Seikei Univ.), Junichi Teruyama (NII), Atsuki Nagao (Kyoto Univ.) COMP2013-52 |
We give efficient algorithms for Sorting $k$-Sets in Bins. The Sorting $k$-Sets in Bins problem can be described as f... [more] |
COMP2013-52 pp.81-85 |
| COMP | 2013-12-21 13:20 |
Okinawa | Okinawa Industry Support Center | k-Edge-Rigid Body-Hinge Graphs Yuya Higashikawa, Naoki Katoh, Yuki Kobayashi (Kyoto Univ.), Adnan Sljoka (York Univ.) COMP2013-53 |
In this paper, we prove that a body-hinge graph $G$ is $(k-1)$-edge-rigid if and only if $G$ is $k$-edge-connected ($k g... [more] | COMP2013-53 pp.87-91 |
| COMP | 2013-12-21 13:45 |
Okinawa | Okinawa Industry Support Center | k-Sink Location Problem in Dynamic Path Networks Yuya Higashikawa (Kyoto Univ.), Mordecai J. Golin (HKUST), Naoki Katoh (Kyoto Univ.) COMP2013-54 |
This paper considers the $k$-sink location problem in dynamic path networks. In our model, a dynamic path network consi... [more] |
COMP2013-54 pp.93-97 |
| COMP | 2013-12-21 14:30 |
Okinawa | Okinawa Industry Support Center | A New Automaton Construction using Prefixes and Suffixes of Regular Expressions Hiroaki Yamamoto (Shinshu Univ.) COMP2013-55 |
[more] | COMP2013-55 pp.99-106 |
| COMP | 2013-12-21 14:55 |
Okinawa | Okinawa Industry Support Center | On alternation-bounded alternating context-free grammars and languages Etsuro Moriya (Waseda Univ.) COMP2013-56 |
Alternating context-free grammars, in which the number of alternations between existential and universal modes is bounde... [more] | COMP2013-56 pp.107-114 |
| COMP | 2013-12-21 15:20 |
Okinawa | Okinawa Industry Support Center | On the minimum consistent DFA problem for prefix samples Kaori Ueno (Tohokui Univ.), Shinichi Shimozono (Kyushu Inst. of Tech.), Kazuyuki Narisawa, Ayumi Shinohara (Tohokui Univ.) COMP2013-57 |
We study the computational complexity of nding the minimum deterministic nite automaton (DFA) that is consistent with ... [more] | COMP2013-57 pp.115-122 |
[Return to Top Page]