記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Germany   Trier   2023年09月18日  -  2023年09月21日

Given a set of persistence diagrams P1,.., Pm, for the data reduction purpose, one way to summarize their topological features is to compute the center C of them first under the bottleneck distance. Here we mainly focus on the two discrete versions when points in C could be selected with or without replacement from all Pi ’s. (We will briefly discuss the continuous case, i.e., points in C are arbitrary, which turns out to be closely related to the 3-dimensional geometric assignment problem). For technical reasons, we first focus on the case when | Pi| ’s are all the same (i.e., all have the same size n), and the problem is to compute a center point set C under the bottleneck matching distance. We show, by a non-trivial reduction from the Planar 3D-Matching problem, that this problem is NP-hard even when m= 3 diagrams are given. This implies that the general center problem for persistence diagrams under the bottleneck distance, when all Pi ’s possibly have different sizes, is also NP-hard when m≥ 3. On the positive side, we show that this problem is polynomially solvable when m= 2 and admits a factor-2 approximation for m≥ 3. These positive results hold for any Lp metric when all Pi ’s are point sets of the same size, and also hold for the case when all Pi ’s have different sizes in the L∞ metric (i.e., for the Center Persistence Diagram problem). This is the best possible in polynomial time for Center Persistence Diagram under the bottleneck distance unless P = NP. All these results hold for both of the discrete versions and the continuous version; in fact, the NP-hardness and approximation results also hold under the Wasserstein distance for the continuous version.

DOI： 10.1007/978-3-031-43587-4_19

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85174604917&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s1 · · · sn over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S′ of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S∗ of S such that the length |S∗| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time k+1/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 2/3 to 4/3.

DOI： 10.4230/LIPIcs.CPM.2023.2

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85165971942&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Cyprus   Larnaca   2023年06月14日  -  2023年06月16日

In this paper, we study a type of incremental optimization variant of the Maximum Independent Set problem (MaxIS), called Bounded-Deletion Maximum Independent Set problem (BD-MaxIS): Given an unweighted graph (formula presented), an initial feasible solution (i.e., an independent set), and a non-negative integer k, the objective of BD-MaxIS is to find an independent set such that and |S| is maximized. The original MaxIS is generally NP-hard, but, it can be solved in polynomial time for perfect graphs (and therefore, comparability, co-comparability, bipartite, chordal, and interval graphs). In this paper, we show that BD-MaxIS is NP-hard even if the input is restricted to bipartite graphs, and hence to comparability graphs. On the other hand, fortunately, BD-MaxIS on co-comparability, interval, convex bipartite, and chordal graphs can be solved in polynomial time. Finally, we study the computational complexity on very similar variants of the Minimum Vertex Cover and the Maximum Clique problems for graph subclasses.

DOI： 10.1007/978-3-031-30448-4_4

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85161382364&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V, E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r ≥ 3) and planar graphs, as follows: (1) For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(r d-1)-approximation and O(r d-2|d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(r d-2|d)-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

DOI： 10.1587/transfun.2021DMP0017

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85138237602&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Austria   Vienna   2022年08月22日  -  2022年03月26日

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least k vertices is considered long. When k ≤ 3, the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4, the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394k+O(1))-approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4. Both algorithms are based on local improvement, and their performance analyses are done via amortization.

DOI： 10.4230/LIPIcs.MFCS.2022.53

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85137607403&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.

DOI： 10.1007/s10878-022-00865-y

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85129866178&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Czech Republic   Prague   2022年06月27日  -  2022年06月29日

The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this paper, we study four variants of LCS: the Repetition-Bounded Longest Common Subsequence problem (RBLCS) [2], the Multiset-Restricted Common Subsequence problem (MRCS) [11], the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS) [5, 6]. Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225n)-time, dynamic programming (DP)-based algorithm for RBLCS was proposed [2], where the two input sequences have lengths n and poly(n). We first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422n) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422n) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS.

DOI： 10.4230/LIPIcs.CPM.2022.15

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85134335577&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Indonesia   Jember   2022年03月24日  -  2022年03月26日

In this paper, we investigate the complexity of the Maximum Happy Set problem on subclasses of co-comparability graphs. For a graph G and its vertex subset S, a vertex v∈ S is happy if all v’s neighbors in G are contained in S. Given a graph G and a non-negative integer k, Maximum Happy Set is the problem of finding a vertex subset S of G such that | S| = k and the number of happy vertices in S is maximized. In this paper, we first show that Maximum Happy Set is NP-hard even for co-bipartite graphs. We then give an algorithm for n-vertex interval graphs whose running time is O(k2n2); this improves the best known running time O(kn8) for interval graphs. We also design an algorithm for n-vertex permutation graphs whose running time is O(k3n2). These two algorithmic results provide a nice contrast to the fact that Maximum Happy Set remains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.

DOI： 10.1007/978-3-030-96731-4_13

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85127916934&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Indonesia   Jember   2022年03月24日  -  2022年03月26日

For a graph G= (V, E), a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v∈ V is contained in exactly one path of P. The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover (MinPC (MaxPC)), is defined as follows: Let U= { 0, 1, ⋯, n- 1 }. Given a graph G= (V, E) and a weight function f: U→ R∪ { + ∞, - ∞}, which defines a weight for each path in its length, MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and PL be the set of paths such that each path is of length ℓ∈ L. We especially consider MinPLPC with 0–1 cost, i.e., the cost function is f(ℓ) = 1 if ℓ∈ L; otherwise f(ℓ) = 0. We also consider MaxPLPC with f(ℓ) = ℓ+ 1, if ℓ∈ L; otherwise f(ℓ) = 0. That is, MaxPLPC is to maximize the number of vertices contained in the paths with length ℓ∈ L in a path cover. In this paper, we first show that MinP{ 0, 1, 2 }PC is NP-hard for planar bipartite graphs of maximum degree three. This implies that (i) for any constant σ≥ 1, there is no polynomial-time approximation algorithm with approximation ratio σ for MinP{ 0, 1, 2 }PC unless P = NP, and (ii) MaxP{3,⋯,n-1}PC is NP-hard for the same graph class. Next, (iii) we present a polynomial-time algorithm for MinP{0,1,⋯,k}PC on graphs with bounded treewidth for a fixed k. Lastly, (iv) we present a 4-approximation algorithm for MaxP{3,⋯,n-1}PC, which becomes a 2.5-approximation for subcubic graphs.

DOI： 10.1007/978-3-030-96731-4_32

Kyutacar

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85127927085&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

In the degree-constrained graph orientation problem, the input is an unweighted, undirected graph G=(V,E) and nonnegative integers av and bv (with av≤bv) for each v∈V, and the objective is to assign a direction to every edge in E in such a way that for each v∈V, the number of outgoing edges in the resulting directed graph lies in the interval [av,bv]. When such an orientation does not exist, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes the total penalty ∑v∈Vcv, where cv is a penalty incurred whenever a vertex v violates its degree constraints. As penalty functions, convex, concave, and step functions are considered in this paper. We show that the problem with any convex penalty function can be solved in O(|E|1.5min⁡{log⁡(|E|⋅C),|E|0.5log⁡Δlog⁡|E|}) time, where Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, we show APX-hardness of the problem with step or concave functions. For trees and graphs with treewidth τ, the problem with any penalty function can be solved exactly in O(|V|log⁡Δ) time and O(τ2Δ2τ+2|V|) time, respectively. Finally, we consider the generalization of the problem to edge-weighted graphs and establish strong bounds on its inapproximability that hold even in the special case of stars. On the positive side, we can extend our algorithms for unweighted version of the problem to obtain pseudo-polynomial-time algorithms for the edge-weighted problem variant when restricted to trees and graphs with bounded treewidth. Also, we design a PTAS and a linear-time algorithm for stars with further restrictions on the degree constraints and edge weights.

DOI： 10.1016/j.tcs.2021.11.019

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85121005850&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

In this paper we study the parameterized complexity for the MAXIMUM HAPPY SET problem (MaxHS): For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k, by neighborhood diversity, or by cluster deletion number.

DOI： 10.1016/j.dam.2021.07.005

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85111074192&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiamčik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree Δ is acyclically edge (Δ+2)-colorable. Despite many milestones, the conjecture remains open even for planar graphs. In this paper, we confirm affirmatively the conjecture on planar graphs without intersecting triangles. We do so by first showing, by discharging methods, that every planar graph without intersecting triangles must have at least one of the six specified groups of local structures, and then proving the conjecture by recoloring certain edges in each such local structure and by induction on the number of edges in the graph.

DOI： 10.1016/j.tcs.2021.06.017

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85108570509&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

In this paper we study the approximability of the MAXIMUM HAPPY SET problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.

DOI： 10.1016/j.tcs.2021.03.023

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85103285503&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices' resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges, H admits an orientation optimizing some objective involving the vertices' outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

DOI： 10.1142/S012905412150012X

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85100564645&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

This paper studies the following variant of clustering or laying out problems for directed acyclic graphs (DAG for short), called the minimum block transfer problem. The objective of this problem is to find a partition of a node set which satisfies the following two conditions: (i) Each element (called a block) of the partition has a size that is at most B and (ii) the maximum number of external arcs among directed paths from the roots to the leaves is minimized. Here, an external arc is defined as an arc connecting two distinct blocks. This paper mainly studies the case B=2. First, we show that the problem is NP-hard even if the height of DAGs is three and its maximum indegree and outdegree are two and three, respectively. Then, we design (i) linear-time optimal algorithms for DAGs of height at most two, (ii) a very simple 2-approximation algorithm, and moreover, (iii) a (2−2∕h)-approximation algorithm for the case that the height h of the input DAG is even and the other one for odd h, whose approximation ratio is 2−2∕(h+1). As for the inapproximability of the problem, for any ε>0 and unless P = NP, we show that the problem does not admit any polynomial time (3∕2−ε)-approximation ((4∕3−ε)-approximation, resp.) algorithm if the height of the input DAGs is restricted to at most five (at least six, resp.). Also, in the case B≥3, we show the NP-hardness and prove a (3∕2−ε)-inapproximability of this case.

DOI： 10.1016/j.dam.2020.08.005

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85089947887&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2020 Elsevier B.V. The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity.

DOI： 10.1016/j.tcs.2020.07.013

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85088399688&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2020 Elsevier B.V. In this paper, we study exact, exponential-time algorithms for a variant of the classic LONGEST COMMON SUBSEQUENCE problem called the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (or RBLCS, for short): Let an alphabet S be a finite set of symbols and an occurrence constraint Cocc be a function Cocc:S→N, assigning an upper bound on the number of occurrences of each symbol in S. Given two sequences X and Y over the alphabet S and an occurrence constraint Cocc, the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s∈S appears at most Cocc(s) times in the obtained subsequence. The special case where Cocc(s)=1 for every symbol s∈S is known as the REPETITION-FREE LONGEST COMMON SUBSEQUENCE problem (RFLCS) and has been studied previously; e.g., in [1], Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS. However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that |X|≤|Y| and |X|=n. In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O(1.44225n). Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O(1.44225n) for any occurrence constraint Cocc, and even less in certain special cases. In particular, for RFLCS, our DP-based algorithm runs in O(1.41422n) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.

DOI： 10.1016/j.tcs.2020.07.042

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85089290906&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

China   Changsha   2020年10月18日  -  2020年10月20日

© 2020, Springer Nature Switzerland AG. An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiamčik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree is acyclically edge -colorable. Despite many milestones, the conjecture is still unknown true or not even for planar graphs. In this paper, we first show by discharging methods that every planar graph without intersecting triangles must have one of the six specified groups of local structures; then by induction on the number of edges we confirm affirmatively the conjecture on planar graphs without intersecting triangles.

DOI： 10.1007/978-3-030-59267-7_36

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85093844290&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

Copyright © 2020 The Institute of Electronics, Information and Communication Engineers This paper introduces the maximization version of the kpath vertex cover problem, called the Maximum k-Path Vertex Cover problem (MaxPkVC for short): A path consisting of k vertices, i.e., a path of length k − 1 is called a k-path. If a k-path Pk includes a vertex v in a vertex set S, then we say that v or S covers Pk. Given a graph G = (V, E) and an integer s, the goal of MaxPkVC is to find a vertex subset S ⊆ V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs. We prove that MaxP3VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.

DOI： 10.1587/transfun.2019DMP0014

Kyutacar

Scopus

CiNii Article

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85094115859&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Atlanta (Online conference)   2020年08月29日  -  2020年08月31日

© 2020, Springer Nature Switzerland AG. In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph and a subset of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph and an integer k, the goal of MaxHS is to find a subset of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a-approximation algorithm for MaxHS on graphs with maximum degree. Next, we show that the approximation ratio can be improved to if the input is a connected graph and its maximum degree is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to proper interval graphs, or block graphs. We prove nevertheless that MaxHS remains NP-hard even for bipartite graphs or for cubic graphs.

DOI： 10.1007/978-3-030-58150-3_27

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85091112536&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Singapore (Online)   2020年03月31日  -  2020年04月02日

© Springer Nature Switzerland AG 2020. In this paper we introduce the Maximum Happy Set problem (MaxHS) and study its parameterized complexity: For an undirected graph G = (V,E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S; and otherwise unhappy. Given an undirected graph G = (V,E) and an integer k, the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard when parameterized by k. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by the tree-width, the clique-width and k, the neighborhood diversity, or the twin-cover number.

DOI： 10.1007/978-3-030-39881-1_27

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85080915754&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

China   Xiamen   2019年12月13日  -  2019年12月15日

© 2019, Springer Nature Switzerland AG. In this paper, we study exact, exponential-time algorithms for a variant of the classic Longest Common Subsequence problem called the r-Repetition Longest Common Subsequence problem (or r-RLCS, for short): Given two sequences X and Y over an alphabet S, find a longest common subsequence of X and Y such that each symbol appears at most r times in the obtained subsequence. Without loss of generality, we will assume that from here on. The special case of 1-RLCS, also known as the Repetition-Free Longest Common Subsequence problem (RFLCS), has been studied previously; e.g., in [1], Adi et al. presented an (exponential-time) integer linear programming-based exact algorithm for 1-RLCS. However, they did not analyze its time complexity, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. In this paper, we first propose a simple algorithm for 1-RLCS based on the strategy used in [1] and show explicitly that its running time is bounded by. Next, we provide a DP-based algorithm for r-RLCS and prove that its running time is for any. In particular, our new algorithm runs in time for 1-RLCS, which is faster than the previous one.

DOI： 10.1007/978-3-030-36412-0_1

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85078537609&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

In this paper, we consider two distance-based relaxed variants of the maximum clique problem (Max Clique), named Maxd-Clique and Maxd-Club for positive integers d.

DOI： 10.1007/s12626-019-00036-2

Kyutacar

その他リンク： https://link.springer.com/article/10.1007/s12626-019-00036-2

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

Copyright © 2019 The Institute of Electronics, Information and Communication Engineers. In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is ( 34d − 18 + 16d3−8 ). In this paper, we design a ( 23d + 13)-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d ≥ 6.

DOI： 10.1587/transfun.E102.A.1142

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85072671695&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

South Korea   Seoul   2019年04月19日  -  2019年04月21日

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

China   Sanya   2019年04月29日  -  2019年05月03日

© Springer Nature Switzerland AG 2019. The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices’ resulting outdegrees; or: (Type II) the maximum or minimum outdegree of all vertices under an optimal orientation of H is minimum or maximum among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

DOI： 10.1007/978-3-030-18126-0_4

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85065303648&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2017 Elsevier B.V. In the parallel k-stage flow-shops problem, we are given m identical k-stage flow-shops and a set of jobs. Each job can be processed by any one of the flow-shops but switching between flow-shops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling (where k=1) and the classical flow-shop scheduling (where m=1) problems, and thus it is NP-hard. We present a polynomial-time approximation scheme (PTAS) for the problem, when m and k are fixed constants. The key technique is to partition the jobs into big jobs and small jobs, enumerate over all feasible schedules for the big jobs, and handle the small jobs by solving a linear program and employing a “sliding” method. Such a technique has been used in the design of PTAS for several flow-shop scheduling variants. Our main contributions are the non-trivial application of this technique and a valid answer to the open question in the literature.

DOI： 10.1016/j.tcs.2017.09.018

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85030666333&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Australia   Melbourne   2018年07月01日  -  2018年07月04日

© Springer International Publishing AG, part of Springer Nature 2018. In this paper we consider the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short) and an integer B, the objective is to find a mapping of its nodes into blocks of size at most B that minimizes the maximum number of external arcs during traversals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. This paper focuses on the case B= 2. Even if B= 2 and the height of the DAG is three, it is known that the problem is NP-hard, and furthermore, there is no 3/2-ε factor approximation algorithm for B= 2 and a small positive ε unless P = NP. On the other hand, the best approximation ratio previously shown is 3. In this paper we improve the approximation ratio into strictly smaller than 2. Also, we investigate the relationship between the height of input DAGs and the inapproximability, since the above inapproximability bound 3/2-ε is shown only for DAGs of height 3.

DOI： 10.1007/978-3-319-95165-2_43

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049964687&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2017, Springer Science+Business Media, LLC. In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Maxd-Clique and Maxd-Club: A d-clique in a graph G= (V, E) is a subset S⊆ V of vertices such that for every pair of vertices u, v∈ S, the distance between u and v is at most d in G. A d-club in a graph G= (V, E) is a subset S ′ ⊆ V of vertices that induces a subgraph of G of diameter at most d. Given a graph G with n vertices, the goal of Maxd-Clique (Maxd-Club, resp.) is to find a d-clique (d-club, resp.) of maximum cardinality in G. Since Max 1-Clique and Max 1-Club are identical to Max Clique, the inapproximabilty for Max Clique shown by Zuckerman in 2007 is transferred to them. Namely, Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n 1 - ε for any ε > 0 unless P= NP. Also, in 2002, Marinc ˘ ek and Mohar showed that it is NP-hard to approximate Maxd-Club to within a factor of n 1 / 3 - ε for any ε > 0 and any fixed d≥ 2. In this paper, we strengthen the hardness result; we prove that, for any ε > 0 and any fixed d≥ 2 , it is NP-hard to approximate Maxd-Club to within a factor of n 1 / 2 - ε . Then, we design a polynomial-time algorithm which achieves an optimal approximation ratio of O(n 1 / 2 ) for any integer d≥ 2. By using the similar ideas, we show the O(n 1 / 2 ) -approximation algorithm for Maxd-Clique for any d≥ 2. This is the best possible in polynomial time unless P= NP, as we can prove the Ω(n 1 / 2 - ε ) -inapproximability.

DOI： 10.1007/s00453-017-0344-y

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025447600&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2017, Springer Science+Business Media New York. The Maximum Happy Vertices (MHV) problem and the Maximum Happy Edges (MHE) problem are two fundamental problems arising in the study of the homophyly phenomenon in large scale networks. Both of these two problems are NP-hard. Interestingly, the MHE problem is a natural generalization of Multiway Uncut, the complement of the classic Multiway Cut problem. In this paper, we present new approximation algorithms for MHV and MHE based on randomized LP-rounding technique and non-uniform approach. Specifically, we show that MHV can be approximated within 1Δ+1/g(Δ), where Δ is the maximum vertex degree and g(Δ)=(Δ+Δ+1)2Δ, and MHE can be approximated within 12+24f(k)≥0.8535, where f(k) ≥ 1 is a function of the color number k. These results improve over the previous approximation ratios for MHV, MHE as well as Multiway Uncut in the literature.

DOI： 10.1007/s00453-017-0302-8

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85015975538&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Morocco   Marrakesh   2018年04月11日  -  2018年04月13日

© 2018, Springer International Publishing AG, part of Springer Nature. The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity.

DOI： 10.1007/978-3-319-96151-4_5

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85050623726&origin=inward

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）

Kyutacar

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2018 The Institute of Electronics, Information and Communication Engineers. In this paper, we study a variant of the Minimum Dominating Set problem. Given an unweighted undirected graph G = (V, E) of n = |V| vertices, the goal of the Minimum Single Dominating Cycle problem (MinSDC) is to find a single shortest cycle which dominates all vertices, i.e., a cycle C such that for the set V(C) of vertices in C and the set N(V(C)) of neighbor vertices of C, V(G) = V(C) ∪ N(V(C)) and |V(C)| is minimum over all dominating cycles in G [6], [17] , [24]. In this paper we consider the (in)approximability of MinSDC if input graphs are restricted to some special classes of graphs. We first show that MinSDC is still NP-hard to approximate even when restricted to planar, bipartite, chordal, or r-regular (r ≥ 3). Then, we show the (ln n + 1)-approximability and the (1 - ϵ) ln n-inapproximability of MinSDC on split graphs under P ≠ NP. Furthermore, we explicitly design a linear-time algorithm to solve MinSDC for graphs with bounded treewidth and estimate the hidden constant factor of its running time-bound.

DOI： 10.1587/transinf.2017FCP0007

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85042631622&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Bangladesh   Dhaka   2018年03月03日  -  2018年03月05日

© 2018, Springer International Publishing AG, part of Springer Nature. This paper introduces the maximum version of the k-path vertex cover problem, called the Maximum k-Path Vertex Cover problem (MaxP k VC for short): A path consisting of k vertices, i.e., a path of length k-1 is called a k-path. If a k-path P k includes a vertex v in a vertex set S, then we say that S or v covers P k . Given a graph G=(V,E) and an integer s, the goal of MaxP k VC is to find a vertex subset S=C of at most s vertices such that the number of k-paths covered by S is maximized. MaxP k VC is generally NP-hard. In this paper we consider the tractability/intractability of MaxP k VC on subclasses of graphs: We prove that MaxP 3 VC and MaxP 4 VC remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP 3 VC can be solved in polynomial time.

DOI： 10.1007/978-3-319-75172-6_21

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85043347936&origin=inward

記述言語：英語   掲載種別：記事・総説・解説・論説等（その他）

CiNii Research

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Hong Kong   Hong Kong   2017年05月05日  -  2017年05月07日

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Hong Kong   Hong Kong   2017年05月05日  -  2017年05月07日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Taiwan   Hsinchu   2017年03月29日  -  2017年03月31日

© Springer International Publishing AG 2017. For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V,E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of Maximum Distance-d Independent Set problem (MaxDdIS) is to find a maximum-cardinality distance-d independent set of G. In this paper we focus on MaxD3IS on cubic (3-regular) graphs. For every fixed integer d ≥ 3, MaxDdIS is NP-hard even for planar bipartite graphs of maximum degree three. Furthermore, when d = 3, it is known that there exists no σ-approximation algorithm for MaxD3IS oncubic graphs for constant σ < 1. 00105. On the other hand, the previously best approximation ratio known for MaxD3IS on cubic graphs is 2. In this paper, we improve the approximation ratio into 1.875 for MaxD3IS on cubic graphs.

DOI： 10.1007/978-3-319-53925-6_18

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014231181&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Japan   Sapporo   2016年08月25日  -  2016年08月26日

© 2016 IEEE. In this paper we consider two distance-based relaxed variants of the maximum clique problem (MAX CLIQUE), named MAX d-CLIQUE and MAX d-CLUB: A d-clique in a graph G is a subset S V(G) of vertices such that for pairs of vertices u, v ϵ S, the distance between u and v is at most d in G. A d-club in a graph G is a subset S' V(G) of vertices that induces a subgraph of G of diameter at most d. MAX d-CLIQUE and MAX d-CLUB ask to find a maximum d-clique and a maximum d-club in a given unweighted graph, respectively. MAX 1-CLIQUE and MAX 1-CLUB cannot be efficiently approximated within a factor of n1-ϵ for any ϵ > 0 unless P = NP since they are identical to MAX CLIQUE [1], [2]. Also, it is known [3], [4] that it is NP-hard to approximate MAX d-CLIQUE and MAX d-CLUB to within a factor of n1/2-ϵ for any fixed d ≥ 2 and any ϵ > 0. As for approximability of MAX d-CLIQUE and MAX d-CLUB, [3] proposes a polynomial-time algorithm, called ByFindStard, and proves that its approximation ratio is O(n1/2) and O(n2/3) for any even d ≥ 2 and for any odd d ≥ 3, respectively. Very recently, a polynomial-time algorithm, called ByFindStar2d, achieving an optimal approximation ratio of O(n1/2) for MAX d-CLIQUE and MAX d-CLUB is designed for any odd d ≥ 3 in [4]. In this paper we implement those approximation algorithms and evaluate their quality empirically for random graphs Gn,p, which have n vertices and each edge appears with probability p. The experimental results show that (i) ByFindStar2d of approximation ratio O(n1/2) can find larger d-clubs (d-cliques) than ByFindStard of approximation ratio O(n2/3) for odd d, (ii) the size of d-clubs (d-cliques) output by ByFindStard is the same as ones by ByFindStar2d for even d, and (iii) ByFindStard can find the same size of d-clubs (d-cliques) much faster than ByFindStar2d.

DOI： 10.1109/SCIS-ISIS.2016.0193

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010409273&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Japan   Hakodate   2016年08月30日  -  2016年08月31日

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Japan   Hakodate   2016年08月30日  -  2016年08月31日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

Copyright © 2016 The Institute of Electronics, Information and Communication Engineers. In this paper we discuss approximation algorithms for the ELEMENT-DISJOINT STEINER TREE PACKING problem (Element-STP for short). For a graph G = (V, E) and a subset of nodes T ⊆ V, called terminal nodes, a Steiner tree is a connected, acyclic subgraph that contains all the terminal nodes in T. The goal of Element-STP is to find as many element-disjoint Steiner trees as possible. Element-STP is known to be APX-hard even for |T| = 3 [1]. It is also known that Element-STP is NP-hard to approximate within a factor of Ω(log |V|) [3] and there is an O(log |V|)-approximation algorithm for Element-STP [2], [4]. In this paper, we provide a ⌈|T|/2⌉-approximation algorithm for Element-STP on graphs with |T| terminal nodes. Furthermore, we show that the approximation ratio of 3 for Element-STP on graphs with five terminal nodes can be improved to 2.

DOI： 10.1587/transfun.E99.A.1059

Kyutacar

Scopus

CiNii Article

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85009396497&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Taiwan   Taipei   2016年05月14日  -  2016年05月16日

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Taiwan   Taipei   2016年05月14日  -  2016年05月16日

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2014, Springer Science+Business Media New York. A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAXW-LIGHT, MINW-LIGHT, MAXW-HEAVY, and MINW-HEAVY take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).

DOI： 10.1007/s00224-014-9565-5

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84952985070&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing Switzerland 2016. In the parallel k-stage flow-shops problem, we are given m identical k-stage flow-shops and a set of jobs. Each job can be processed by any one of the flow-shops but switching between flow-shops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling (where k = 1) and the classical flow-shop scheduling (where m = 1) problems, and thus it is NP-hard. We present a polynomial-time approximation scheme for the problem, when m and k are fixed constants. The key technique is to enumerate over schedules for big jobs, solve a linear programming for small jobs, and add the fractional small jobs at the end. Such a technique has been used in the design of similar approximation schemes.

DOI： 10.1007/978-3-319-39817-4_22

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84976608271&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing AG 2016. This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V,E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r ≥ 3) and planar graphs, as follows: (1) For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd−1)-approximation and O(rd−2/d)- approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd−2/d)-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

DOI： 10.1007/978-3-319-48749-6_20

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85007188790&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

CiNii Research

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

CiNii Research

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

CiNii Research

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

© Journal of Graph Algorithms and Applications. This paper introduces four graph orientation problems named MAXIMIZE W-LIGHT, MINIMIZE W-LIGHT, MAXIMIZE W-HEAVY, and MINIMIZE W-HEAVY, where W can be any fixed non-negative integer. In each problem, the input is an undirected, unweighted graph G and the objective is to assign a direction to every edge in G so that the number of vertices with outdegree at most W or at least W in the resulting directed graph is maximized or minimized. A number of results on the computational complexity and polynomial-time approximability of these problems for different values of W and various special classes of graphs are derived. In particular, it is shown that MAXIMIZE 0-LIGHT and MINIMIZE 1-HEAVY are identical to MAXIMUM INDEPENDENT SET and MINIMUM VERTEX COVER, respectively, so by allowing the value of W to vary, we obtain a new generalization of the two latter problems.

DOI： 10.7155/jgaa.00371

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951278348&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Houston   2015年12月18日  -  2015年12月20日

© Springer International Publishing Switzerland 2015. A d-clique in a graph G=(V,E) is a subset S⊆V of vertices such that for pairs of vertices u,v∈S, the distance between u and v is at most d in G. A d-club in a graph G=(V,E) is a subset S′⊆V of vertices that induces a subgraph of G of diameter at most d. Given a graph G with n vertices, the goal of Max d-Clique (Max d-Club, resp.) is to find a d-clique (d-club, resp.) of maximum cardinality in G. Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n1−ε for any ε>0 unless P=NP since they are identical to Max Clique [14, 21]. Also, it is known [3] that it is NP-hard to approximate Max d-Club to within a factor of n1/2−ε for any fixed d≥2 and for any ε>0. As for approximability of Max d-Club, there exists a polynomial-time algorithm which achieves an optimal approximation ratio of O(n1/2) for any even d≥2 [3]. For any odd d≥3, however, there still remains a gap between the O(n2/3)-approximability and the Ω(n1/2−ε)-inapproximability for Max d-Club [3]. In this paper, we first strengthen the approximability result for Max d-Club; we design a polynomial-time algorithm which achieves an optimal approximation ratio of O(n1/2) for Max d-Club for any odd d≥3. Then, by using the similar ideas, we show the O(n1/2)-approximation algorithm for Max d-Clique on general graphs for any d≥2. This is the best possible in polynomial time unless P=NP, as we can prove the Ω(n1/2−ε)-inapproximability. Furthermore, we study the tractability of Max d-Clique and Max d-Club on subclasses of graphs.

DOI： 10.1007/978-3-319-26626-8_43

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951990304&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2014 Elsevier B.V. We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[. S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.

DOI： 10.1016/j.tcs.2014.07.008

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84926407099&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Canada   Vancouver   2014年07月08日  -  2014年07月10日

In this paper we discuss approximation algorithms for the Element-Disjoint Steiner Tree Packing problem (Element-STP for short). For a graph G = (V, E) and a subset of nodes T ⊆ V, called terminal nodes, a Steiner tree is a connected, acyclic subgraph that contains all the terminal nodes in T. The goal of Element-STP is to find as many element-disjoint Steiner trees as possible. Element-STP is known to be APX-hard even for |T| = 3 [1]. It is also known that Element-STP is NP-hard to approximate within a factor of Ω(log|V|) [3] and there is an O(log|V|)-approximation algorithm for Element-STP [2,4]. In this paper, we provide a ⌈|T|/2⌉-approximation algorithm for Element-STP on graphs with |T| terminal nodes. Furthermore, we show that the approximation ratio of 3 for Element-STP on graphs with five terminal nodes can be improved to 2. © 2014 Springer International Publishing.

DOI： 10.1007/978-3-319-07956-1_10

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84903940800&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

China   Hangzhou   2014年05月17日  -  2014年05月19日

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Japan   Kitakyushu   2014年12月03日  -  2014年12月06日

© 2014 IEEE. In this paper we propose new variants of the Evolutionary Algorithms, called Multi-Virus Evolutionary Algorithm (MVEA) and Multi-Virus Evolutionary Annealing Algorithm (MVEA2) for the following pursuit problem. Given a set of mobile agents and a set of mobile targets in a map as an input instance, the goal of the agents is to pursue and capture as many mobile targets by cooperating with other agents as possible, and furthermore as quickly as possible. When we use the multipoint search algorithms such as Genetic Algorithms (GAs) and Virus Evolutionary Algorithms (VEA) for optimization problems, it is important to keep the diversity of the search points. To improve the diversity, MVEA selects several viruses of inferior individuals with a certain probability, and moreover, MVEA2 blends the simulated annealing heuristic (SA) with MVEA. In this paper, we show the detailed experimental comparisons among the performances of a traditional GA, GA with SA, MVEA, and MVEA2 on the number of captured mobile targets and the number of the required steps for agents to capture all the mobile targets in the pursuit problem. The comparisons show that (i) MVEA and MVEA2 behave in similar ways as GA and GA with SA, respectively, and (ii) GA with SA and MVEA2 does not work better in the early stages than GA and MVEA, but especially in the final stages, the former algorithms can capture the larger number of mobile targets than one of the latter ones.

DOI： 10.1109/SCIS-ISIS.2014.7044840

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84946531071&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

France   Sophia Antipolis   2013年09月05日  -  2013年09月06日

A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in [4]: For any fixed non-negative integer W, the problems Max W -Light, Min W -Light, Max W -Heavy, and Min W -Heavy take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. The problems' computational complexities vary with W. Here, we resolve several open questions related to their polynomial-time approximability and present a number of positive and negative results. © 2014 Springer International Publishing.

DOI： 10.1007/978-3-319-08001-7_3

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84903631659&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

The paper studies a generalization of the Independent Set problem (IS for short). A distance- d independent set for an integer d≥2 in an unweighted graph G = (V, E) is a subset S⊂ V of vertices such that for any pair of vertices u, v εS, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the Distance- d Independent Set problem (D d IS for short) is to decide whether G contains a distance- d independent set S such that |S| ≥k. D2IS is identical to the original IS. Thus D2IS is \mathcal{NP} -complete even for planar graphs, but it is in \mathcal{P} for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D d IS, its maximization version MaxD d IS, and its parameterized version ParaD d IS(k), where the parameter is the size of the distance- d independent set: (1) We first prove that for any ε >0 and any fixed integer d≥3, it is \mathcal{NP} -hard to approximate MaxD d IS to within a factor of n1/2- for bipartite graphs of n vertices, and for any fixed integer d≥3, ParaD d IS(k) is \mathcal{W}[1] -hard for bipartite graphs. Then, (2) we prove that for every fixed integer d≥3, D d IS remains NP -complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d≥2, whereas D d IS is NP -complete for any odd d≥3. Also, we show the hardness of approximation of MaxD d IS and the W[1] -hardness of ParaD d IS(k) on chordal graphs for any odd d≥3. © 2013 Springer Science+Business Media New York.

DOI： 10.1007/s10878-012-9594-4

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84893764641&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

Consider a rooted directed acyclic graph G=(V,E) with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper shows the tight bound on the (in)approximability under the assumption P≠NP: we present a polynomial time approximation algorithm with factor (1-1/e), and show that there exists no polynomial time approximation algorithm with a better constant factor than (1-1/e) unless P=NP. © 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.05.018

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84884286822&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

This paper studies the online Orthogonal Variable Spreading Factor (OVSF) code assignment problem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270-281, 2004). We propose a (1+1/α)-competitive algorithm with help of (1+⌈α⌉) lg* - h trees for the height h of the OVSF code tree and any α≥1. In other words, it is a (1+ε)-competitive algorithm with help of (1+⌈1/ε⌉)lg* - h trees for any constant 0<ε≤1. In the case of α=1 (or ε=1), we obtain a 2-competitive algorithm with 2lg* - h trees, which substantially improves the previous resource of 3h/8+2 trees shown by Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358-367, 2009). In another aspect, if it is not necessary to bound the incurred cost for individual requests to a constant, an amortized (4/3+δ)-competitive algorithm with (11/4+4/(3δ)) trees for any 0<δ≤4/3 is also designed in Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358-367, 2009). The algorithm in this paper gives us a new trade-off between the competitive ratio and the resource augmentation when α≥3 (or ε≤1/3), although the incurred cost for individual requests is bounded to a constant. © 2012 Springer Science+Business Media, LLC.

DOI： 10.1007/s10878-012-9454-2

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84886438763&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

England   Liverpool   2013年08月19日  -  2013年08月21日

We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs. © 2013 Springer-Verlag.

DOI： 10.1007/978-3-642-40164-0_6

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84883179628&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Korea   Suwon   2013年07月12日  -  2013年07月13日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Japan   Matsushima   2013年04月19日  -  2013年04月21日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

Given a connected graph G = (V, E) on n vertices, the Maximum r-Regular Induced Connected Subgraph (r-MaxRICS) problem asks for a maximum sized subset of vertices S ⊆ V such that the induced subgraph G[S] on S is connected and r-regular. It is known that 2-MaxRICS and 3-MaxRICS are NP-hard. Moreover, 2-MaxRICS cannot be approximated within a factor of n1-ε in polynomial time for any ε > 0 unless P = NP. In this paper, we show that r-MaxRICS are NP-hard for any fixed integer r ≥ 4. Furthermore, we show that for any fixed integer r ≥ 3, r-MaxRICS cannot be approximated within a factor of n1/6-ε in polynomial time for any ε > 0 unless P = NP. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

DOI： 10.1587/transinf.E96.D.443

Kyutacar

Scopus

CiNii Article

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84878238046&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Canada   Banff   2012年08月05日  -  2012年08月09日

The paper studies a generalization of the Independent Set (IS) problem. A distance-d independent set for a positive integer d ≥ 2 in an unweighted graph G = (V, E) is a set S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the Distance- d Independent Set (D d IS) problem is to decide whether G contains a distance-d independent set S such that |S| ≥ k. D2IS is identical to the original IS and thus D2IS is in for bipartite graphs and chordal graphs. In this paper, we show that for every fixed integer d ≥ 3, D d IS is -complete even for planar bipartite graphs of maximum degree three, and also -complete even for chordal bipartite graphs. Furthermore, we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d ≥ 2, whereas D d IS is -complete for any odd d ≥ 3. © 2012 Springer-Verlag.

DOI： 10.1007/978-3-642-31770-5_21

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84865023969&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Australia   Melbourne   2012年01月30日  -  2012年02月02日

Given an undirected graph G = (V,E), a graph orientation problem is to decide a direction for each edge so that the resulting directed graph G = (V, Λ(E)) satisfies a certain condition, where Λ(E) is a set of assignments of a direction to each edge {u, v} ∈ E. Among many conceivable types of conditions, we consider a degree constrained orientation: Given positive integers a v and b v for each v (a v ≤ b v), decide an orientation of G so that a v ≤ {pipe}{(v, u) ∈ Λ(E)}{pipe} ≤ b v holds for every v ∈ V. However, such an orientation does not always exist. In this case, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes Σ v∈Vcv, where c v is a penalty incurred for v's violating the degree constraint. As penalty functions, several classes of functions can be considered, e.g., linear functions, convex functions and concave functions. We show that the degree-constrained orientation with any convex (including linear) penalty function can be solved in O(m 1:5 min{Δ 0:5, log(nC)}), where n = {pipe}V{pipe},m = {pipe}E{pipe}, Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, it has no polynomial approximation algorithm whose approximation factor is better than 1.3606, for concave penalty functions, unless P=NP; it is APX-hard. This holds even for step functions, which are considered concave. For trees, the problem with any penalty functions can be solved exactly in O(n log Δ) time, and if the penalty function is convex, it is solvable in linear time. © 2012, Australian Computer Society, Inc.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84864023399&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Japan   Tokyo   2012年07月10日  -  2012年07月11日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

An instance of the sorting buffer problem (SBP) consists of a sequence of requests for service, each of which is specified by a point in a metric space, and a sorting buffer which can store up to a limited number of requests and rearrange them. To serve a request, the server needs to visit the point where serving a request p following the service to a request q requires the cost corresponding to the distance d(p,q) between p and q. The objective of SBP is to serve all input requests in a way that minimizes the total distance traveled by the server by reordering the input sequence. In this paper, we focus our attention to the uniform metric, i.e., the distance d(p,q)=1 if p≠q, d(p,q)=0 otherwise, and present the first NP-hardness proof for SBP on the uniform metric. © 2012 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.dam.2012.02.005

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84859923903&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

We study the problem of embedding an unweighted complete binary tree into a line with low distortion. Very recently, Mathieu and Papamanthou (2008) [9] showed that the inorder traversal of the complete binary tree of height h gives a line embedding of distortion O(2 h), and conjectured that the current lower bound of Ω(2 hh) increases to Ω(2 h), i.e., the upper bound of O(2 h) is best possible. In this paper, we disprove their conjecture by providing a line embedding of the complete binary tree of height h with optimal distortion Θ(2 hh). © 2012 Elsevier B.V. © 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ipl.2012.02.003

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84857425777&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

China   Shanghai   2012年04月21日  -  2012年04月22日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

China   Shanghai   2012年04月21日  -  2012年04月22日

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Greece   Athens   2012年04月19日  -  2012年04月21日

This paper introduces four graph orientation problems named Maximize W -Light, Minimize W -Light, Maximize W -Heavy, and Minimize W -Heavy, where W can be any fixed non-negative integer. In each of these problems, the input is an undirected graph G and the objective is to assign a direction to each edge in G so that the number of vertices with outdegree at most W or at least W in the resulting directed graph is maximized or minimized. We derive a number of results on the computational complexity and polynomial-time approximability of these problems for different values of W and various special classes of graphs. In particular, we show that Maximize 0-Light and Minimize 1-Heavy are equivalent to Maximum Independent Set and Minimum Vertex Cover, respectively, so by allowing the value of W to vary, we obtain a new, natural generalization of the two latter problems. © 2012 Springer-Verlag.

DOI： 10.1007/978-3-642-32147-4_30

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84865205428&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

We consider new variants of the vertex/edge domination problems on graphs. A vertex is said to dominate itself and its all adjacent vertices, and similarly an edge is said to dominate itself and its all adjacent edges. Given an input graph G = (V;E) and an integer k, the κ-Vertex (κ-Edge) Maximum Domination (κ-MaxVD and κ-MaxED, respectively) is to find a subset D V ⊆ V of vertices (resp., D E ⊆ E of edges) with size at most k that maximizes the cardinality of dominated vertices (resp., edges). In this paper, we first show that a simple greedy strategy achieves an approximation ratio of (1 - 1=e) for both k-MaxVD and κ-MaxED. Then, we show that this approximation ratio is the best possible for κ-MaxVD unless P = NP. We also prove that, for any constant ε > 0, there is no polynomial time 1303=1304+ε approximation algorithm for κ-MaxED unless P = NP. However, if k is not larger than the size of the minimum maximal matching, κ-MaxED is 3/4-approximable in polynomial time. Copyright © 2011, Australian Computer Society, Inc.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84864629153&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Richardson, TX   2011年08月14日  -  2011年08月16日

This paper studies the online Orthogonal Variable Spreading Factor (OVSF) code assignment problem with resource augmentation introduced by Erlebach et al. in [8]. We propose a (1 + ε)-competitive algorithm with help of (1 + ⌈1/ε⌉) lg* h trees for the height h of the OVSF code tree and any constant 0 < ε ≤ 1. In the case of ε = 1, we obtain a 2-competitive algorithm with 2lg* h trees, which substantially improves the previous resource of 3h/8 + 2 trees shown by Chan et al. in [2]. © 2011 Springer-Verlag.

DOI： 10.1007/978-3-642-22685-4_24

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=80051974886&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Las Vegas   2011年07月18日  -  2011年07月21日

記述言語：日本語   掲載種別：記事・総説・解説・論説等（大学・研究所紀要）

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=79957991709&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

Given a simple, undirected graph G = (V ,E) and a weight function w : E→ℤ+, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1, k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1 + 1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2-1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1, k} within a ratio of 3/2 for k = 2 (note that this matches the inapproximability bound above), and (2 -2/(k +1)) for any k ≤ 3, respectively, in polynomial time. © Springer Science+Business Media, LLC 2009.

DOI： 10.1007/s10878-009-9276-z

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=79955053720&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Taiwan   Hsinchu   2011年04月16日  -  2011年04月17日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Taiwan   Hsinchu   2011年04月16日  -  2011年04月17日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P4-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for seriesparallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth. © 2010 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2010.11.003

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=79952185117&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. This problem is closely related to the job scheduling on parallel machines, called the machine covering problem, where its goal is to assign jobs to parallel machines such that each machine is covered as much as possible. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 ε for any constant ε > 0 in polynomial time unless P=NP, even if all edge weights belong to {1, 2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time wmax/wmin-approximation algorithm for MAXMINO where wmax and wmin denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wmin is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph. © 2011 World Scientific Publishing Company.

DOI： 10.1142/S0129054111008246

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=79955055443&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Oaxaca   2010年07月12日  -  2010年07月15日

主要論文集（会議） 代表的研究業績

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Maxico   Oaxaca   2010年04月19日  -  2010年04月23日

The paper studies the maximum diameter-bounded subgraph problem (MaxDBS for short) which is defined as follows: Given an n-vertex graph G and a fixed integer d ≥ 1, the goal is to find its largest subgraph of the diameter d. If d=1, the problem is identical to the maximum clique problem and thus it is script NP-hard to approximate MaxDBS to within a factor of n 1-ε for any ε > 0. Also, it is known to be NP-hard to approximate MaxDBS to within a factor of n 1/3-ε for any ε > 0 and a fixed d ≥ 2. In this paper, we first strengthen the hardness result; we prove that, for any ε > 0 and a fixed d ≥ 2, it is script NP-hard to approximate MaxDBS to within a factor of n 1/2-ε . Then, we show that a simple polynomial-time algorithm achieves an approximation ratio of n 1/2 for any even d ≥ 2, and an approximation ratio of n 2/3 for any odd d ≥ 3. Furthermore, we investigate the (in)tractability and the (in)approximability of MaxDBS on subclasses of graphs, including chordal graphs, split graphs, interval graphs, and k-partite graphs. © 2010 Springer-Verlag.

DOI： 10.1007/978-3-642-12200-2_53

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77953518539&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. We assume that all the unknown graphs are undirected and connected. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher's task is to visit all the nodes and go back to the starting node by traveling a tour as short as possible. One of the simplest strategies is the nearest neighbor algorithm (NN), which always chooses the unvisited node nearest to the searcher's current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm to explore cycles is better than 1.25-competitive. © 2009 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ipl.2009.10.013

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=71249091196&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Italy   Rome   2009年05月25日  -  2009年05月29日

We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. This problem is closely related to the job scheduling on parallel machines, called the machine covering problem, where its goal is to assign jobs to parallel machines such that each machine is covered as much as possible. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 - ε for any constant ε > 0 in polynomial time unless P-NP, even if all edge weights belong to {1,2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time Wmax/Wmin-approximation algorithm for MAXMINO where wmax and wmin denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wmin is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph. © 2009 IEEE.

DOI： 10.1109/IPDPS.2009.5160872

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=70449823954&origin=inward

担当区分：責任著者   記述言語：日本語   掲載種別：研究論文（大学，研究機関等紀要）

CiNii Article

その他リンク： https://ci.nii.ac.jp/naid/110007105610

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

China   Hangzhou   2008年04月11日  -  2008年04月12日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity. (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is \mathcal{NP} -hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability. © 2008 Springer Science+Business Media, LLC.

DOI： 10.1007/s00224-008-9117-y

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=59549087080&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

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. Copyright © 2009 The Institute of Electronics, Information and Communication Engineers.

DOI： 10.1587/transinf.E92.D.130

Kyutacar

Scopus

CiNii Article

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77950347126&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Orland   2008年07月13日  -  2008年07月17日

An instance of the sorting buffer problem (SBP) consists of a sequence of requests for service, each of which is specified by a point in a metric space, and a sorting buffer which can store up to a limited number of requests and rearrange them. To serve a request, the server needs to visit the point where serving a request p following the service to a request q requires the cost corresponding to the distance d(p, q) between p and q. The objective of SBP is to serve all input requests in a way that minimizes the total distance traveled by the server by reordering the input sequence. In this paper we focus our attention to the uniform metric, i.e., the distance d(p, q) = 1 if p ≠ q, d(p, q) = 0 otherwise, and present the first NP-hardness proof for SBP on the uniform metric.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=62649104698&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

China   Hong Kong   2008年04月26日  -  2008年04月27日

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

This paper studies the following variant of the Vehicle Routing Problem that we call the Grasp and Delivery for Moving Objects (GDMO) problem, motivated by robot navigation: The input to the problem consists of n products, each of which moves on a predefined path with a fixed constant speed, and a robot arm of capacity one. In each round, the robot arm grasps one product and then delivers it to the depot. The goal of the problem is to find a collection of tours such that the robot arm grasps and delivers as many products as possible. In this paper we prove the following results: (i) If the products move on broken lines with at least one bend, then the GDMO is MAXSNP-hard, and (ii) it can be approximated with ratio 2. However, (iii) if we impose the "straight line without bend" restriction on the motion of every product, then the GDMO becomes tractable. © 2007 Springer Science+Business Media, LLC.

DOI： 10.1007/s00224-007-9081-y

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=38949156542&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Australia   Wollongong   2008年01月26日  -  2008年01月31日

Given an undirected graph with edge weights, we are asked to find an orientation, i.e., an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tight thresholds of complexity: We show that MMO is (i) in P for cactuses, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for P4-bipartite graphs. The latter two are minimal superclasses of the former. Also, we show the NP-hardness for the other related graph classes, diamond-free, house-free, series-parallel, bipartite and planar. © 2008, Australian Computer Society, Inc.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84863591626&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Czech Republic   Harrachov   2007年01月20日  -  2007年01月26日

In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher's task is to visit all the nodes and go back to the starting node by traveling as a short tour as possible. One of the simplest strategies is the nearest neighbor algorithm (NN), which always chooses the unvisited node nearest to the searcher's current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm is better than 1.25-competitive. © Springer-Verlag Berlin Heidelberg 2007.

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=38149016113&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Italy   Castiglioncello   2007年06月03日  -  2007年06月05日

A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity, (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is NP-hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability. © Springer-Verlag Berlin Heidelberg 2007.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=38049061587&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Portland, OR   2007年06月06日  -  2007年06月08日

Given an undirected graph G = (V, E) and a weight function w : E → ℤ+, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. In this paper (1) we prove that the problem is strongly NP-hard if all edge weights belong to the set {1 ,k}, where k is any integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1 + 1/k) unless P=NP; (2) we present a polynomial time algorithm that approximates the general version of the problem within a factor of (2 - 1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1, k} within a factor of 3/2 for k = 2 (note that this matches the inapproximability bound above), and (2 - 2/(k + 1)) for any k ≥ 3, respectively, in polynomial time. © Springer-Verlag Berlin Heidelberg 2007.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=38149071598&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Czech Republic   2007年08月26日  -  2007年08月31日

Consider a rooted directed acyclic graph G = (V, E) with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper presents a polynomial time approximation algorithm with factor (1 -1/e), and shows that there exists no polynomial time approximation algorithm with a better constant factor than (1-1/e) unless NP ⊆ DTIME(NO(log log N)), where N is the size of the inputs. © Springer-Verlag Berlin Heidelberg 2007.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=38049040864&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

This paper studies the problem of orienting all edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be AP-hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, min{w max/wmin, (2 - ε)}-approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and ε is some small positive real number that depends on the input. © World Scientific Publishing Company.

DOI： 10.1142/S0129054107004644

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=34247237820&origin=inward

記述言語：日本語   掲載種別：記事・総説・解説・論説等（学術雑誌）

CiNii Article

その他リンク： https://ci.nii.ac.jp/naid/110006240366

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Czech Republic   2006年08月30日  -  2006年09月01日

代表的研究業績

Kyutacar

記述言語：英語   掲載種別：研究論文（学術雑誌）

In difficult classification problems of the z-dimensional points into two groups giving 0-1 responses due to the messy data structure, we try to find the denser regions for the favorable customers of response 1, instead of finding the boundaries to separate the two groups. Such regions are called the bumps, and finding the boundaries of the bumps is called the bump hunting. The main objective of this paper is to find the largest region of the bumps under a specified ratio of the number of the points of response 1 to the total. Then, we may obtain a trade-off curve between the number of points of response 1 and the specified ratio. The decision tree method with the Gini's index will provide the simple-shaped boundaries for the bumps if the marginal density for response 1 shows a rather simple or monotonic shape. Since the computing time searching for the optimal trees will cost much because of the NP-hardness of the problem, some random search methods, e.g., the genetic algorithm adapted to the tree, are useful. Due to the existence of many local maxima unlike the ordinary genetic algorithm search results, the extreme-value statistics will be useful to estimate the global optimum number of captured points; this also guarantees the accuracy of the semi-optimal solution with the simple descriptive rules. This combined method of genetic algorithm search and extreme-value statistics use is new. We apply this method to some artificial messy data case which mimics the real customer database, showing a successful result. The reliability of the solution is discussed. Copyright © 2006 The Institute of Electronics, Information and Communication Engineers.

DOI： 10.1093/ietisy/e89-d.8.2332

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=33747829503&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Italy   Rome   2006年05月29日  -  2006年05月31日

The paper studies the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short), the objective is to find a mapping of its nodes into blocks of size at most B that minimizes the maximum number of external arcs during traversals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. The problem can be shown to be NP-hard generally, and to remain intractable even if B = 2 and the height of DAGs is three. In this paper we provide a 3/2 factor linear time approximation algorithm for B = 2, and prove that the 3/2 ratio is optimal in terms of approximation guarantee. In the case of B ≥ 3, we also show that there is no 3/2 - ε factor approximation algorithm assuming P ≠ NP, where ε is arbitrarily small positive. Furthermore, we give a 2 factor approximation algorithm for B = 3 if the input is restricted to a set of layered graphs. © Springer-Verlag Berlin Heidelberg 2006.

DOI： 10.1007/11758471_27

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=33746104069&origin=inward

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）

2006年01月  -  2006年01月

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Australia   Hobart, Tasmania   2006年01月16日  -  2006年01月19日

We study the problem of orienting the edges of a weighted graph such that the maximum weighted out- degree of vertices is minimized. This problem, which has applications in the guard arrangement for ex-ample, can be shown to be NP-hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, or more generally, a graph with identically weighted edges, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a sim-ple, combinatorial, min{wmax/wmin ; (2-ε)g-approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and " is some small positive real number that depends on the input. © 2008, Australian Computer Society, Inc.

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84863571152&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Suppose that we are interested in classifying the points into two groups giving 0-1 responses in z-dimensional space which corresponds to z explanation variables. So far a lot of classification tools which adopt the misclassification rate to evaluate how well the discrimination be achieved have been proposed and played a key role in the field of statistical learning or data mining. In the real world, however, we often encounter the cases that the mis-classification rate remains considerably high no matter how carefully we search for the discriminating boundaries if we want to capture the points to some extent with rather simpler rules. In such a messy case, the optimization criterion in classification goes to obtaining the larger number of points of response 1, we are interested in, with a specified pureness rate. Such a region is called to be a bump or a hotspot. Our primary objective is to find the bumps. To use the information of the boundaries of the bumps with ease, it would be beneficial that the bumps have much simpler shapes of their boundaries such as the z-dimensional box located parallel to some explanation variable axes. The problem raised is, however, how to find such a boundary for some bump. The decision tree algorithms find the splitting point for an explanation variable to construct much purer sub-regions using the entropy or the Gini's index criterion, from the top node to the bottom leafs step by step. Regarding that to produce the purer regions is just the same as to exclude those regions, this splitting criterion may also be applicable to produce the denser region for response 1 including response 0 points to some extent. This paper deals with this point. Mimicking the real data case in a customer database of a correspondence course in Japan, we investigate the fundamental data cases such that the marginal distributions for response 1 are rather simple shaped, such as monotonie or unimodal, and those for response 0 is almost uniformly distributed. The unimodal and monotonie cases are studied by using the normal distributions located at the center of and on the corner of the uniform distributions, respectively. Under such restricted conditions, we have found that the Gini's index can detect the boundaries for the bumps as if eyes of human beings do so.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77952184919&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Italy   Siena   2005年10月12日  -  2005年10月14日

We consider the following variant of the Vehicle Routing Problem that we call the Pickup and Delivery for Moving Objects (PDMO) problem, motivated by robot navigation: The input to the problem consists of n products, each of which moves on a predefined path with a fixed constant speed, and a robot arm of capacity one. In each round, the robot arm grasps and delivers one product to its original position. The goal of the problem is to find a collection of tours such that the robot arm grasps and delivers as many products as possible. In this paper we prove the following results: (i) If the products move on broken lines with at least one bend, then the PDMO is MAXSNP-hard, and (ii) it can be approximated with ratio two. However, (iii) if we impose the "straight line without bend" restriction on the motion of every product, then the PDMO becomes tractable. © Springer-Verlag Berlin Heidelberg 2005.

DOI： 10.1007/11560586_5

Kyutacar

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=33646185829&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Orland   2005年07月10日  -  2005年07月13日

In this paper, we consider a formalization of the following scheduling problem motivated by a variety of practical applications: The input to the problem consists of a robot arm of capacity k (i.e., it can grasp at most k products at a time) and n products, each of which is associated with a release time and a deadline and moves on a predefined path with a fixed constant speed. In each round (tour), the robot arm grasps at most k products by their deadlines and delivers to a specified delivery point. The goal of the problem is to find a collection of tours such that the robot arm of capacity k grasps by their deadlines and delivers as many products as possible. In this paper we show that there is an O(nα(n) log n) algorithm for the case k = 1 if all the products move on given straight lines with faster speeds than the robot arm, where α(n) is the inverse Ackermann function. However, for the similar setting for the paths of the products, we prove that if some of the products' speeds are slower than the robot arm's one, then the problem remains NP-hard.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84867380300&origin=inward

担当区分：責任著者   記述言語：日本語   掲載種別：研究論文（大学，研究機関等紀要）

CiNii Article

その他リンク： https://ci.nii.ac.jp/naid/110000942833

担当区分：責任著者   記述言語：日本語   掲載種別：研究論文（大学，研究機関等紀要）

CiNii Article

その他リンク： https://ci.nii.ac.jp/naid/110000167398

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

An O(N)oblivious permutation-routing algorithm for two-dimensional meshes is presented. The model is a standard mesh where N×N processors are connected via point-to-point connections and each processor has four queues, one per each outgoing link, which can hold only a constant number of temporal packets. The previous bound was O(N0.75) (K. Iwama, Y. Kambayashi, and E. Miyano, in “Proc. 6th European Symposium on Algorithms,” pp. 295¿306, 1998).

DOI： 10.1006/jagm.2001.1176

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

The mesh of buses (MBUS) is a parallel computation model which consists of n × n processors, n row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutation) routing on MBUSs, the known 1.5n upper bound appears to be hard to improve. Also, the information theoretic lower bound for any type of MBUS routing is 1.0n. In this paper, we present two randomized algorithms for MBUS routing. One of them runs in 1.4375n + o(n) steps with high probability. The other runs 1.25n + o(n) steps also with high probability but needs more local computation. © 2001 Elsevier Science B.V. All rights reserved.

DOI： 10.1016/S0304-3975(00)00141-9

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0034918297&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

This paper shows an important exception to the common perception that three-dimensional meshes are more powerful than two-dimensional ones. Let N be the total number of processors. Then permutation routing over three-dimensional mesh computers needs Θ(N2/3) steps while it takes Θ(N1/2) steps over two-dimensional ones under the following conditions: (1) The path of each packet must be determined solely by its initial position and destination, i.e., the algorithm must be oblivious. (2) Each path must be "elementary," i.e., it must be shortest and as straight as possible. Thus the conditions, under which, somewhat surprisingly, three-dimensional meshes are significantly less powerful than two-dimensional ones for the fundamental network operation, are quite reasonable in practice. © 2001 Academic Press.

DOI： 10.1006/jagm.2000.1152

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0346251600&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

We give two, new upper bounds for oblivious permutation routing on the mesh networks: Let N be the total number of processors in each mesh. One is an O(N0.75) algorithm on the two-dimensional, √N × √N mesh with constant queue-size. This is the first algorithm which improves substantially the trivial O(N) bound for oblivious routing in the mesh networks with constant queue-size. The other is a 1.16√N +o(√N) algorithm on the three-dimensional, N1/3×N1/3×N 1/3 mesh with unlimited queue-size. This algorithm allows at most three bends in the path of each packet. If the number of bends is restricted to minimal, i.e., at most two, then the bound jumps to Ω(N2/3) as was shown in ESA'97.

DOI： 10.7155/jgaa.00038

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=4043074744&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

USA   Bar Harbor, Maine   2000年07月09日  -  2000年07月13日

A deterministic, oblivious, permutation routing algorithm on the 2D meshes of constant queue size is presented. An optimal, linear-time bound for oblivious permutation routing could be obtained for these meshes. A new algorithm based on bit-reversal permutation for oblivious routing is proposed. A (2.954+ε)n oblivious routing is proposed where ε is any positive constant and the queue-size is a function of ε. The running time of the algorithm is less than 1.5 times as large as the network diameter of the mesh. The n×n mesh is considered and model on these meshes are presented. The problems in controlling the pipeline of packet flows is discussed.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0033651418&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

SUMMARY The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture processors are naturally placed at intersections of horizontal and vertical grids while there can be three different types of communication links: (i) The first type is the most popular model called a mesh-connected computer: Each processor is connected to its four neighbours by local connections (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms with pointers to the literature and suggests further research directions for mesh routing. key words: parallel computation meshes packet routing.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0034157021&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

An optimal ⌈1.5N1/2⌉ lower bound is shown for oblivious routing on the mesh of buses: a two-dimensional parallel model consisting of N1/2×N1/2 processors and N1/2 row and N1/2 column buses but no local connections between neighboring processors. Many lower bound proofs for routing on mesh-structured models use a single instance (adversary) which includes difficult packet-movement. This approach does not work in our case; our proof is one of the rare cases which really exploit the fact that the routing algorithm has to cope with many different instances. Note that the two-dimensional mesh of buses includes 2N1/2 buses and each processor can access two different buses. Apparently the three-dimensional model provides more communication facilities, namely including 3N2/3 buses, and each processor can access three different buses. Surprisingly, however, the oblivious routing on the three-dimensional mesh of buses needs more time, i.e., Ω(N2/3) steps, which is another important result of this paper. © 2000 Academic Press.

DOI： 10.1006/jpdc.1999.1597

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0042493312&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Czech Republic   Prague   1999年07月16日  -  1999年07月18日

© Springer-Verlag Berlin Heidelberg 1999. Our model in this paper is the standard, two-dimensional n×n mesh. The first result is a randomized algorithm for h-h routing which runs in O(hn) steps with high probability using queues of constant size. The previous bound is 0:5hn + o(hn) but needs the queue-size of Ω(h). An important merit of this algorithm is to give us improved bounds by applying several schemes of faulty-mesh routing. For example, the scheme by [Rag95], originally O(n log n) time and O(log2 n) queue-size, gives us an improved routing algorithm on p-faulty meshes (p ≤ 0:4) which runs in O(n/log2 n/k) time using O(k) queue-size for any k ≤ log n. Thus, when k = log n it improves the queue-size by the factor of log n without changing the time bound and when k is constant, it needs only constant queue-size although the running time slows down by the factor of log n.

DOI： 10.1007/3-540-48481-7_6

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84958093162&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Baltimore, Maryland   1999年01月  -  1999年01月

その他リンク： https://www.scopus.com/record/display.uri?eid=2-s2.0-0032784736&origin=resultslist&sort=plf-f&src=s&sid=55110e4e924b208767cac7afc3866fd8&sot=autdocs&sdt=autdocs&sl=17&s=AU-ID%286603649200%29&relpos=68&citeCnt=4&searchTerm=

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Italy   Venice   1998年08月24日  -  1998年08月26日

We give two, new upper bounds for oblivious permutation routing on the mesh network. One is an O(N0.75) algorithm for the two-dimensional mesh with constant queue-size. This is the first algorithm which improves substantially the trivial O(N) bound. The other is an 1.16√N + o(√N) algorithm on the three-dimensional mesh with unlimited queue-size. This algorithm allows at most three bends in the path of each packet. If the number of bends is restricted to minimal, i.e., at most two, then the bound jumps to Ω(N2/3) as was shown in ESA'97. © Springer-Verlag Berlin Heidelberg 1998.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84896797252&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Taiwan, R.o.C   Taipei   1998年08月12日  -  1998年08月14日

© Springer-Verlag Berlin Heidelberg 1998. The mesh of buses (MBUS) is a parallel computation model which consists of n × n processors, n row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutation) routing on MBUSs, the known 1.5n upper bound appears to be hard to improve. Also, the information theoretic lower bound for any type of MBUS routing is 1.0n. In this paper, we present two randomized algorithms for MBUS routing. One of them runs in 1.4375n+o(n) steps with high probability. The other runs 1.25n+o(n) steps also with high probability but needs more local computation.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84949009019&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

Although there have been a lot of efforts to seek nice characterization of non-Hamiltonian graphs, little progress has been made so far. An important progress was achieved by Chvátal [5, 6] who introduced the class of non-1-tough graphs (N1T) and the class of non-sub-2-factor graphs (NS2F). Both contain only non-Hamiltonian graphs and the conditions for membership can be checked in non-deterministic polynomial time. Also it is known that N1T⊆NS2F. Chvátal posed an open question about the complexity of those classes, i.e., whether or not they are NP-complete [6]. Recently, Bauer et al. [2] proved that N1T is NP-complete. In this paper we prove: (i) NS2F is also NP-complete. (ii) NS2F - N1T is DP-complete, namely, the former characterization for non-Hamiltonian graphs is essentially better than the latter, (iii) Those results are still true for the bounded-degree graphs.

DOI： 10.1016/S0166-218X(97)00099-1

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0042856686&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Switzerland   Geneva   1997年04月01日  -  1997年04月05日

An optimal [1.5N 1/2 ] lower bound is shown for oblivious routing on the mesh of buses, a two-dimensional parallel model consisting of N1/2×N1/2 processors, N1/2 row and N1/2 column buses but no local connections between neighbouring processors. Many lower bound proofs for routing on mesh-structured models use a single instance (adversary) which includes difficult packet-movement. This approach does not work in our case; our proof is the first which exploits the fact that the routing algorithm has to cope with many different instances. Note that the two-dimensional mesh of buses includes 2N1/2 buses and each processor can access two different buses. Apparently the three-dimensional model provides more communication facilities, namely, including 3N2/3 buses and each processor can access three different buses. Surprisingly, however, the oblivious routing on the three-dimensional mesh of buses needs more time, i.e., Ω(N2/3) steps, which is another important result of this paper.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0030645691&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Austria   Graz   1997年09月15日  -  1997年09月17日

© 1997, Springer Verlag, All Rights Reserved. This paper shows an important exception against the common perception that three-dimensional meshes are more powerful than two-dimensional ones: Let N be the total number of processors. Then permutation routing over three-dimensional mesh computers needs θ(N 2/3) steps while it takes θ(N 1/2) steps over two-dimensional ones under the following condition: (1) The path of each packet must be determined solely by its initial position and destination, i.e., the algorithm must be oblivious. (2) Each path must be "elementary," i.e., it must be shortest and as straight as possible. Thus the conditions are quite reasonable in practice, under which, little surprisingly, three-dimensional meshes are significantly less powerful than two-dimensional ones for the fundamental network operation.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84949230059&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

The mesh of buses (MBUSs) is a parallel computation model which consists of n × n processors, n row buses, and n column buses, but no local connections between neighboring processors. An n lower bound for the permutation routing on this model is shown. The proof does not depend on common predetermined assumptions such as "if a packet has to move horizontally then it has to ride on a horizontal bus at least once." As for upper bounds, a 1.5n algorithm is shown. © 1996 Academic Press, Inc.

DOI： 10.1006/jagm.1996.0030

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0030361349&origin=inward

記述言語：日本語   掲載種別：研究論文（大学，研究機関等紀要）

記述言語：日本語   掲載種別：研究論文（大学，研究機関等紀要）

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Minneapolis, Minnesota   1995年06月19日  -  1995年06月22日

Read-once resolution (ROR) is a resolution proof system in which the rule (A + x)(B + x̄) → (A + B) is applied in such a way that two clauses (A + x) and (B + x̄) are replaced by (A + B), i.e., (A + x) and (B + x̄) disappear, and any clause can never be copied. Therefore ROR runs in (nondeterministic) polynomial time and is no longer complete. In this paper it is shown that, in spite of its simplicity and weak power, ROR is still intractable: (1) The problem whether a CNF formula can be proved by ROR is NP-complete. (2) Let R(k) be a set of formulas f such that f can be proved by ROR but using up to k copy operations. Then R(k) - R(k - 1) is DP-complete. Thus if we can use one more copy operation then the set of provable formulas enlarges essentially.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0029228107&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   New Jersey   1993年10月  -  1993年10月

記述言語：日本語   掲載種別：研究論文（大学，研究機関等紀要）

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

USA   Stanford   1993年03月  -  1993年03月

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Spain   Madrid   1992年09月  -  1992年09月

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Japan   Nagoya   1992年12月16日  -  1992年12月18日

© Springer-Verlag Berlin Heidelberg 1992. The mesh of buses (MBUSs) is a parallel computation model which consists of n × n processors, n row buses and n column buses. Upper and lower bounds for the routing problem over MBUSs are discussed. We first show elementary upper and lower hounds, 2n and 0.5n, respectively, for its parallel time complexity. The gap between 2n and 0.5n is then narrowed to 1.5n and n, which is the main theme of the paper. The n lower bound might seem to he trivial but is actually not. Three counter examples will be shown against this kind of easy intuition.

DOI： 10.1007/3-540-56279-6_68

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84974775849&origin=inward

開催期間： 2022年09月16日 - 2022年09月17日   記述言語：日本語   開催地：オンライン開催（大会本部：長崎大学）  

開催期間： 2022年09月16日 - 2022年09月17日   記述言語：日本語   開催地：オンライン開催（大会本部：長崎大学）  

開催期間： 2022年09月16日 - 2022年09月17日   記述言語：日本語   開催地：オンライン開催（大会本部：長崎大学）  

開催期間： 2022年02月01日 - 2022年02月03日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2022年02月01日 - 2022年02月03日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2022年01月27日 - 2022年01月28日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年11月13日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2021年09月24日 - 2021年09月25日   記述言語：日本語   開催地：オンライン開催（大会本部：佐賀大学）  

開催期間： 2020年12月04日   記述言語：日本語   開催地：オンライン開催  

開催期間： 2020年11月28日   記述言語：日本語   開催地：博多バスターミナル9F第10・11ホール，福岡市  

開催期間： 2020年11月28日   記述言語：日本語   開催地：博多バスターミナル9F第10・11ホール，福岡市  

開催期間： 2020年11月28日   記述言語：日本語   開催地：博多バスターミナル9F第10・11ホール，福岡市  

開催期間： 2020年11月28日   記述言語：日本語   開催地：博多バスターミナル9F第10・11ホール，福岡市  

開催期間： 2020年11月28日   記述言語：日本語   開催地：博多バスターミナル9F第10・11ホール，福岡市  

開催期間： 2020年09月26日 - 2020年09月27日   記述言語：日本語   開催地：オンライン開催（大会本部：九州産業大学）  

開催期間： 2020年09月26日 - 2020年09月27日   記述言語：日本語   開催地：オンライン開催（大会本部：九州産業大学）  

開催期間： 2020年09月26日 - 2020年09月27日   記述言語：日本語   開催地：オンライン開催（大会本部：九州産業大学）  

開催期間： 2020年02月05日 - 2020年02月07日   記述言語：日本語   開催地：京都大学数理解析研究所  

開催期間： 2019年11月30日   記述言語：日本語   開催地：九工大飯塚キャンパス  

開催期間： 2019年11月28日 - 2019年11月29日   記述言語：日本語   開催地：旧大連航路上屋２Ｆホール /北九州市門司港レトロ内（福岡県北九州市）  

開催期間： 2019年10月26日 - 2019年10月27日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2019年10月26日 - 2019年10月27日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2019年10月26日 - 2019年10月27日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2019年10月26日 - 2019年10月27日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2019年10月26日 - 2019年10月27日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2019年10月26日 - 2019年10月27日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2019年10月26日 - 2019年10月27日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2019年09月27日 - 2019年09月28日   記述言語：日本語   開催地：九州工業大学戸畑キャンパス，北九州  

開催期間： 2019年09月27日 - 2019年09月28日   記述言語：日本語   開催地：九州工業大学戸畑キャンパス，北九州  

開催期間： 2019年09月27日 - 2019年09月28日   記述言語：日本語   開催地：九州工業大学戸畑キャンパス，北九州  

開催期間： 2019年05月10日 - 2019年05月11日   記述言語：日本語   開催地：熊本大学，熊本県熊本市  

開催期間： 2018年12月27日 - 2018年12月28日   記述言語：日本語   開催地：国民宿舎虹ノ松原ホテル，佐賀県唐津市  

開催期間： 2018年12月27日 - 2018年12月28日   記述言語：日本語   開催地：国民宿舎虹ノ松原ホテル，佐賀県唐津市  

開催期間： 2018年10月27日 - 2018年10月28日   記述言語：日本語   開催地：日本文理大学湯布院研修所，大分県由布市  

開催期間： 2018年10月27日 - 2018年10月28日   記述言語：日本語   開催地：日本文理大学湯布院研修所，大分県由布市  

開催期間： 2018年09月18日   記述言語：日本語   開催地：九州工業大学飯塚キャンパス，福岡県飯塚市  

開催期間： 2018年09月18日   記述言語：日本語   開催地：九州工業大学飯塚キャンパス，福岡県飯塚市  

開催期間： 2018年09月03日   記述言語：日本語   開催地：小樽商科大学，北海道小樽市  

開催期間： 2018年02月05日 - 2018年02月07日   記述言語：日本語   開催地：京都大学数理解析研究所，京都府京都市  

開催期間： 2018年02月05日 - 2018年02月07日   記述言語：日本語   開催地：京都大学数理解析研究所，京都府京都市  

開催期間： 2017年12月20日 - 2017年12月21日   記述言語：日本語   開催地：高知工科大学，高知  

開催期間： 2017年10月28日 - 2017年10月29日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2017年10月28日 - 2017年10月29日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2017年10月28日 - 2017年10月29日   記述言語：日本語   開催地： 福岡工業大学FITセミナーハウス，大分県由布市湯布院町  

開催期間： 2017年09月27日 - 2017年09月28日   記述言語：日本語   開催地：琉球大学，那覇  

開催期間： 2017年09月08日   記述言語：英語   開催地：City College of New York, New York, USA  

開催期間： 2017年03月01日 - 2017年03月02日   記述言語：日本語   開催地：鹿児島大学  

開催期間： 2017年03月01日 - 2017年03月02日   記述言語：日本語   開催地：鹿児島大学  

開催期間： 2016年10月29日 - 2016年10月30日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス  

開催期間： 2016年10月29日 - 2016年10月30日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス  

開催期間： 2016年10月29日 - 2016年10月30日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス  

開催期間： 2016年10月29日 - 2016年10月30日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス  

開催期間： 2016年09月28日   記述言語：日本語   開催地：宮崎大学  

開催期間： 2016年06月24日 - 2016年06月25日   記述言語：日本語   開催地：石川県教育会館（石川県金沢市）  

開催期間： 2016年03月02日 - 2016年03月03日   記述言語：日本語   開催地：宮崎大学  

開催期間： 2015年10月31日 - 2015年11月01日   記述言語：日本語  

開催期間： 2015年10月31日 - 2015年11月01日   記述言語：日本語  

開催期間： 2015年10月31日 - 2015年11月01日   記述言語：日本語  

開催期間： 2015年10月31日 - 2015年11月01日   記述言語：日本語  

開催期間： 2015年10月02日   記述言語：日本語  

開催期間： 2015年09月10日 - 2015年09月11日   記述言語：日本語   開催地：九州工業大学  

開催期間： 2015年09月10日 - 2015年09月11日   記述言語：日本語   開催地：九州工業大学  

開催期間： 2015年09月04日   記述言語：日本語   開催地：福岡大学  

開催期間： 2015年07月14日 - 2015年07月16日   記述言語：日本語   開催地：ゆのくに天祥（石川県加賀市）  

開催期間： 2015年03月05日 - 2015年03月06日   記述言語：日本語   開催地：佐賀大学  

開催期間： 2015年03月05日 - 2015年03月06日   記述言語：日本語   開催地：佐賀大学  

開催期間： 2014年11月20日 - 2014年11月21日   記述言語：日本語   開催地：大濱信泉記念館  

開催期間： 2014年10月25日 - 2014年10月26日   記述言語：日本語   開催地：旅館魚半  

開催期間： 2014年10月25日 - 2014年10月26日   記述言語：日本語   開催地：旅館魚半  

開催期間： 2014年10月25日 - 2014年10月26日   記述言語：日本語   開催地：旅館魚半  

開催期間： 2014年09月18日 - 2014年09月19日   記述言語：日本語   開催地：鹿児島大学工学部  

開催期間： 2014年09月18日 - 2014年09月19日   記述言語：日本語   開催地：鹿児島大学工学部  

開催期間： 2014年09月18日 - 2014年09月19日   記述言語：日本語   開催地：鹿児島大学工学部  

開催期間： 2014年09月08日 - 2014年09月09日   記述言語：日本語   開催地：玄海ロイヤルホテル  

開催期間： 2014年08月28日 - 2014年08月29日   記述言語：日本語   開催地：北海道科学大学  

開催期間： 2014年07月17日 - 2014年07月19日   記述言語：日本語   開催地：半月庵  

開催期間： 2014年07月17日 - 2014年07月19日   記述言語：日本語   開催地：半月庵  

開催期間： 2014年03月04日 - 2014年03月05日   記述言語：日本語   開催地：大分大学工学部  

開催期間： 2013年12月20日 - 2013年12月21日   記述言語：日本語  

開催期間： 2013年10月26日 - 2013年10月27日   記述言語：日本語   開催地：きらら交流館  

開催期間： 2013年10月26日 - 2013年10月27日   記述言語：日本語   開催地：きらら交流館  

開催期間： 2013年09月24日 - 2013年09月25日   記述言語：日本語   開催地：熊本大学  

開催期間： 2013年09月24日 - 2013年09月25日   記述言語：日本語   開催地：熊本大学  

開催期間： 2013年09月24日 - 2013年09月25日   記述言語：日本語   開催地：熊本大学  

開催期間： 2013年09月24日 - 2013年09月25日   記述言語：日本語   開催地：熊本大学  

開催期間： 2013年09月03日   記述言語：日本語  

開催期間： 2013年07月16日 - 2013年07月18日   記述言語：日本語   開催地：休暇村 志賀島  

開催期間： 2013年07月16日 - 2013年07月18日   記述言語：日本語   開催地：休暇村 志賀島  

開催期間： 2013年07月16日 - 2013年07月18日   記述言語：日本語   開催地：休暇村 志賀島  

開催期間： 2013年05月17日 - 2013年05月18日   記述言語：日本語  

CiNii Article

開催期間： 2013年03月14日 - 2013年03月15日   記述言語：日本語   開催地：熊本大学工学部  

開催期間： 2013年03月14日 - 2013年03月15日   記述言語：日本語   開催地：熊本大学工学部  

開催期間： 2013年03月14日 - 2013年03月15日   記述言語：日本語   開催地：熊本大学工学部  

開催期間： 2012年10月27日 - 2012年10月28日   記述言語：日本語   開催地：北九州市立大学後援会館  

開催期間： 2012年10月27日 - 2012年10月28日   記述言語：日本語   開催地：北九州市立大学後援会館  

開催期間： 2012年10月27日 - 2012年10月28日   記述言語：英語   開催地：北九州市立大学後援会館  

開催期間： 2012年07月17日 - 2012年07月19日   記述言語：日本語  

開催期間： 2012年06月21日   記述言語：日本語  

CiNii Article

開催期間： 2011年12月16日   記述言語：日本語  

開催期間： 2011年11月18日   記述言語：日本語  

開催期間： 2011年10月29日 - 2011年10月30日   記述言語：英語  

開催期間： 2011年10月29日 - 2011年10月30日   記述言語：日本語  

開催期間： 2011年10月29日 - 2011年10月30日   記述言語：日本語  

開催期間： 2011年10月29日 - 2011年10月30日   記述言語：日本語  

開催期間： 2011年09月28日   記述言語：日本語  

開催期間： 2011年09月28日   記述言語：日本語  

開催期間： 2011年06月30日   記述言語：日本語  

開催期間： 2011年03月07日   記述言語：日本語   開催地：日本 那覇  

開催期間： 2010年12月03日   記述言語：英語   開催地：日本 福岡  

開催期間： 2010年09月24日   記述言語：日本語   開催地：日本 福岡  

開催期間： 2010年09月24日   記述言語：日本語   開催地：日本 福岡  

開催期間： 2010年06月25日   記述言語：日本語   開催地：日本 東京  

開催期間： 2010年03月05日   記述言語：日本語   開催地：日本 東京  

開催期間： 2009年09月   記述言語：日本語   開催地：日本 福岡  

開催期間： 2009年09月   記述言語：日本語   開催地：日本 福岡  

開催期間： 2009年05月11日   記述言語：英語   開催地：日本 東京  

開催期間： 2009年03月04日   記述言語：日本語   開催地：日本 福岡  

開催期間： 2009年02月02日 - 2009年02月04日   記述言語：日本語   開催地：日本 京都  

開催期間： 2008年09月   記述言語：日本語   開催地：日本 大分  

開催期間： 2008年09月   記述言語：日本語   開催地：日本 大分  

開催期間： 2008年09月   記述言語：日本語   開催地：日本 大分  

開催期間： 2008年09月   記述言語：日本語   開催地：日本 大分  

開催期間： 2008年05月13日   記述言語：日本語   開催地：日本 福岡  

開催期間： 2008年03月07日   記述言語：日本語   開催地：日本  

開催期間： 2007年11月   記述言語：英語  

開催期間： 2007年09月   記述言語：日本語   開催地：日本 沖縄  

開催期間： 2007年09月   記述言語：日本語   開催地：日本 沖縄  

開催期間： 2007年09月   記述言語：日本語   開催地：日本 沖縄  

開催期間： 2007年09月   記述言語：日本語   開催地：日本 沖縄  

開催期間： 2007年09月   記述言語：日本語   開催地：日本 沖縄  

開催期間： 2007年09月   記述言語：日本語   開催地：日本 沖縄  

開催期間： 2007年05月25日   記述言語：日本語   開催地：日本  

開催期間： 2007年05月25日   記述言語：日本語   開催地：日本  

開催期間： 2006年12月04日   記述言語：日本語   開催地：日本  

開催期間： 2006年09月28日 - 2006年09月29日   記述言語：日本語  

開催期間： 2006年09月28日 - 2006年09月29日   記述言語：日本語  

開催期間： 2006年09月28日 - 2006年09月29日   記述言語：日本語  

開催期間： 2006年04月   記述言語：日本語  

開催期間： 2006年04月   記述言語：英語   開催地：日本  

開催期間： 2006年03月   記述言語：英語  

開催期間： 2005年10月   記述言語：英語   開催地：日本 仙台  

開催期間： 2005年10月   記述言語：日本語   開催地：日本 鹿児島  

開催期間： 2005年07月   記述言語：英語   開催地：日本 福岡  

開催期間： 2005年05月   記述言語：英語   開催地：日本 福岡市  

開催期間： 2005年03月   記述言語：日本語   開催地：日本  

開催期間： 2004年10月14日 - 2004年10月15日   記述言語：日本語   開催地：日本  

開催期間： 2004年06月25日   記述言語：英語   開催地：日本  

開催期間： 2004年04月   記述言語：日本語   開催地：日本  

開催期間： 2004年03月18日   記述言語：英語   開催地：日本  

開催期間： 2004年02月   記述言語：日本語   開催地：日本  

開催期間： 2003年09月   記述言語：日本語   開催地：日本  

開催期間： 2003年04月   記述言語：日本語   開催地：日本  

開催期間： 2002年04月   記述言語：日本語   開催地：日本  

開催期間： 2002年02月03日 - 2002年02月05日   記述言語：日本語   開催地： 京都  

開催期間： 2000年04月   記述言語：日本語   開催地：日本  

開催期間： 2000年04月   記述言語：英語   開催地：日本  

開催期間： 2000年04月   記述言語：日本語   開催地：日本  

開催期間： 1999年05月04日 - 1999年05月05日   記述言語：英語  

開催期間： 1998年07月   記述言語：英語  

開催期間： 1991年05月   記述言語：日本語  

科目区分：学部専門科目

科目区分：学部専門科目

科目区分：学部専門科目

平成29年度若手OR研究交流会

平成28年度若手OR研究交流会

平成27年度若手OR研究交流会
ホロノミック勾配法を用いた項目反応理論の最尤推定計算

平成26年度若手OR研究交流会
ランダムグラフ中の最大クリーク・クラブ・クランのサイズ

若手の会セミナー2014からの選定
次数制約部分グラフ探索問題の計算複雑さ

分散環境に適応させた進化アルゴリズム

部分グラフクラスに対する最大dクラン問題

九州地区における若手ＯＲ研究交流会2012
次数を限定した平面グラフにおける誘導部分グラフ探索問題

九州地区における若手ＯＲ研究交流会2011
対決ゲームモデルの紹介とその拡張

第60回電気関係学会九州支部連合大会からの選定
試問予定表作成問題の制約付きモデルに対するNP困難性