Naoki Katoh

According to our database1, Naoki Katoh authored at least 155 papers between 1981 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2020
Minsum <i>k</i>-sink problem on path networks.
Theor. Comput. Sci., 2020

Minmax Regret 1-Sink Location Problems on Dynamic Flow Path Networks with Parametric Weights.
CoRR, 2020

Almost Linear Time Algorithms for Minsum k-Sink Problems on Dynamic Flow Path Networks.
Proceedings of the Combinatorial Optimization and Applications, 2020

2019
Preface for the Special Issue on the Project "Foundation of Innovative Algorithms for Big Data".
Rev. Socionetwork Strateg., 2019

A Survey on Facility Location Problems in Dynamic Flow Networks.
Rev. Socionetwork Strateg., 2019

On Computing a Center Persistence Diagram.
CoRR, 2019

Minmax-Regret Evacuation Planning for Cycle Networks.
Proceedings of the Theory and Applications of Models of Computation, 2019

2018
Minimax Regret 1-Median Problem in Dynamic Path Networks.
Theory Comput. Syst., 2018

The mixed evacuation problem.
J. Comb. Optim., 2018

Minsum k-Sink Problem on Path Networks.
CoRR, 2018

Minmax Regret 1-Sink for Aggregate Evacuation Time on Path Networks.
CoRR, 2018

Minsum k-Sink Problem on Dynamic Flow Path Networks.
Proceedings of the Combinatorial Algorithms - 29th International Workshop, 2018

An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017
Geometric Graphs: Theory and Applications (NII Shonan Meeting 2017-16).
NII Shonan Meet. Rep., 2017

A population-based algorithm for solving linear assignment problems with two objectives.
Comput. Oper. Res., 2017

Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks.
Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

2016
Extended formulations for sparsity matroids.
Math. Program., 2016

Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs.
Inf. Process. Lett., 2016

Improved Algorithms for Computing k-Sink on Dynamic Path Networks.
CoRR, 2016

Optimal Evacuation Flows on Dynamic Paths with General Edge Capacities.
CoRR, 2016

On the edge crossing properties of Euclidean minimum weight Laman graphs.
Comput. Geom., 2016

2015
Optimally bracing grid frameworks with holes.
Theor. Comput. Sci., 2015

Multiple sink location problems in dynamic path networks.
Theor. Comput. Sci., 2015

Minimax regret 1-sink location problem in dynamic path networks.
Theor. Comput. Sci., 2015

Geometric k-Center Problems with Centers Constrained to Two Lines.
CoRR, 2015

Polynomial-time approximability of the k-Sink Location problem.
CoRR, 2015

A Linear-Time Algorithm for Testing Outer-1-Planarity.
Algorithmica, 2015

Straight-Line Drawability of a Planar Graph Plus an Edge.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Continuous Folding of Regular Dodecahedra.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Geometric p-Center Problems with Centers Constrained to Two Lines.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

2014
An inductive construction of minimally rigid body-hinge simple graphs.
Theor. Comput. Sci., 2014

Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity.
J. Graph Algorithms Appl., 2014

Online graph exploration algorithms for cycles and trees by multiple searchers.
J. Comb. Optim., 2014

The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths.
Discret. Appl. Math., 2014

Improved Algorithms for Multiple Sink Location Problems in Dynamic Path Networks.
CoRR, 2014

2013
A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system.
Theor. Comput. Sci., 2013

Rooted-Tree Decompositions with Matroid Constraints and the Infinitesimal Rigidity of Frameworks with Boundaries.
SIAM J. Discret. Math., 2013

Online Vertex Exploration Problems in a Simple Polygon.
IEICE Trans. Inf. Syst., 2013

Independent arborescences in directed graphs.
Discret. Math., 2013

Minimax Regret 1-Sink Location Problems in Dynamic Path Networks.
Proceedings of the Theory and Applications of Models of Computation, 2013

Emerging Pattern Based Crime Spots Analysis and Rental Price Prediction.
Proceedings of the Contrast Data Mining: Concepts, Algorithms, and Applications, 2013

2012
An Emergency Evacuation Planning Model Using the Universally Quickest Flow.
Rev. Socionetwork Strateg., 2012

A rooted-forest partition with uniform vertex demand.
J. Comb. Optim., 2012

Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time - (Extended Abstract).
Proceedings of the Graph Drawing - 20th International Symposium, 2012

Online Exploration of All Vertices in a Simple Polygon.
Proceedings of the Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, 2012

2011
Collision Probability in an In-Line Machines Model.
Trans. Comput. Sci., 2011

Covering directed graphs by in-trees.
J. Comb. Optim., 2011

A Proof of the Molecular Conjecture.
Discret. Comput. Geom., 2011

2010
A Geometric Spanner of Segments.
Int. J. Comput. Geom. Appl., 2010

2009
Combinatorial Optimization Algorithms in Resource Allocation Problems.
Proceedings of the Encyclopedia of Optimization, Second Edition, 2009

Fast Enumeration Algorithms for Non-crossing Geometric Graphs.
Discret. Comput. Geom., 2009

Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees.
Discret. Appl. Math., 2009

An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths.
Discret. Appl. Math., 2009

Arc-disjoint in-trees in directed graphs.
Comb., 2009

On the Infinitesimal Rigidity of Bar-and-Slider Frameworks.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

A Proof of the Molecular Conjecture.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008
Enumerating Constrained Non-crossing Minimally Rigid Frameworks.
Discret. Comput. Geom., 2008

The Minimum Weight In-Tree Cover Problem.
Proceedings of the Modelling, 2008

Geometric Spanner of Objects under L1 Distance.
Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

2007
Triangulating a convex polygon with fewer number of non-standard bars.
Theor. Comput. Sci., 2007

Risk discovery of car-related crimes from urban spatial attributes using emerging patterns.
Int. J. Knowl. Based Intell. Eng. Syst., 2007

Enumerating Non-crossing Minimally Rigid Frameworks.
Graphs Comb., 2007

Is this brand ephemeral? A multivariate tree-based decision analysis of new product sustainability.
Decis. Support Syst., 2007

Applying graph mining to discover substructures of room layouts which affect the rent of apartments.
Proceedings of the IEEE International Conference on Systems, 2007

Voronoi Diagram with Respect to Criteria on Vision Information.
Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering, 2007

Enumerating Constrained Non-crossing Geometric Spanning Trees.
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

An Efficient Algorithm for the Evacuation Problem in a Certain Class of a Network with Uniform Path-Lengths.
Proceedings of the Algorithmic Aspects in Information and Management, 2007

2006
Polyline Fitting of Planar Points under Min-sum Criteria.
Int. J. Comput. Geom. Appl., 2006

Inserting Points Uniformly at Every Instance.
IEICE Trans. Inf. Syst., 2006

Finding a Triangular Mesh with a Constant Number of Different Edge Lengths.
IEICE Trans. Inf. Syst., 2006

An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity.
IEICE Trans. Inf. Syst., 2006

An approximation algorithm for the pickup and delivery vehicle routing problem on trees.
Discret. Appl. Math., 2006

Preface.
Discret. Appl. Math., 2006

Foreword.
Algorithmica, 2006

Angular Voronoi Diagram with Applications.
Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering, 2006

Polygonal Curve Approximation Using Grid Points with Application to a Triangular Mesh Generation with Small Number of Different Edge Lengths.
Proceedings of the Algorithmic Aspects in Information and Management, 2006

An Efficient Algorithm for Evacuation Problems in Dynamic Network Flows with Uniform Arc Capacity.
Proceedings of the Algorithmic Aspects in Information and Management, 2006

2005
Efficient Algorithms and Implementations for Optimizing the Sum of Linear Fractional Functions, with Applications.
J. Comb. Optim., 2005

Optimal spanners for axis-aligned rectangles.
Comput. Geom., 2005

The Future Direction of New Computing Environment for Exabyte Data in the Business World.
Proceedings of the 2005 IEEE/IPSJ International Symposium on Applications and the Internet Workshops (SAINT 2005 Workshops), 31 January, 2005

Triangulating a Convex Polygon with Small Number of Non-standard Bars.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004
The structure and number of global roundings of a graph.
Theor. Comput. Sci., 2004

On Geometric Structure of Global Roundings for Graphs and Range Spaces.
Proceedings of the Algorithm Theory, 2004

Efficient Algorithms for Approximating a Multi-dimensional Voxel Terrain by a Unimodal Terrain.
Proceedings of the Computing and Combinatorics, 10th Annual International Conference, 2004

2003
Matrix Rounding under the L<sup>p</sup>-Discrepancy Measure and Its Application to Digital Halftoning.
SIAM J. Comput., 2003

Matrix Rounding and Related Problems with Application to Digital Halftoning.
Proceedings of the System Modeling and Optimization, 2003

Use of a Genetic Heritage for Solving the Assignment Problem with Two Objectives.
Proceedings of the Evolutionary Multi-Criterion Optimization, 2003

Business Application for Sales Transaction Data by Using Genome Analysis Technology.
Proceedings of the Discovery Science, 6th International Conference, 2003

Data Mining Oriented CRM Systems Based on MUSASHI: C-MUSASHI.
Proceedings of the Active Mining, Second International Workshop, 2003

2002
Approximating uniform triangular meshes in polygons.
Theor. Comput. Sci., 2002

Parametric Polymatroid Optimization and Its Geometric Applications.
Int. J. Comput. Geom. Appl., 2002

K-Levels of Concave Surfaces.
Discret. Comput. Geom., 2002

Combinatorial and Geometric Problems Related to Digital Halftoning.
Proceedings of the Geometry, 2002

Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

A Machine Learning Algorithm for Analyzing String Patterns Helps to Discover Simple and Interpretable Business Rules from Purchase History.
Proceedings of the Progress in Discovery Science, 2002

2001
A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree.
J. Comb. Optim., 2001

Efficient Algorithms for Optimization-Based Image Segmentation.
Int. J. Comput. Geom. Appl., 2001

A unified scheme for detecting fundamental curves in binary edge images.
Comput. Geom., 2001

The Supported Solutions Used as a Genetic Information in a Population Heuristics.
Proceedings of the Evolutionary Multi-Criterion Optimization, 2001

Notes on computing peaks in k-levels and parametric spanning trees.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000
LMT-skeleton heuristics for several new classes of optimal triangulations.
Comput. Geom., 2000

Optimizing the sum of linear fractional functions and applications.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Approximating Uniform Triangular Meshes for Spheres.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2000

Discovering Interpretable Rules that Explain Customers' Brand Choice Behavior.
Proceedings of the Discovery Science, 2000

1999
Finding Subsets Maximizing Minimum Structures.
SIAM J. Discret. Math., 1999

Lovász's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Approximation of Optimal Two-Dimensional Association Rules for Categorical Attributes Using Semidefinite Programming.
Proceedings of the Discovery Science, 1999

1998
Mining Pharmacy Data Helps to Make Profits.
Data Min. Knowl. Discov., 1998

A Capacitated Vehicle Routing Problem on a Tree.
Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

Convertibility among Grid Filling Curves.
Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

Data Mining Oriented System for Business Applications.
Proceedings of the Discovery Science, 1998

On Computing New Classes of Optimal Trangulations with Angular Constraints.
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

1997
A New Probabilistic Analysis of Karger's Randomized Algorithm for Minimum Cut Problems.
Inf. Process. Lett., 1997

Covering Points in the Plane by <i>k</i>-Tours: Towards a Polynomial Time Approximation Scheme for General <i>k</i>.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996
Triangulations Intersect Nicely.
Discret. Comput. Geom., 1996

A New Unifying Heuristic Algorithm for the Undirected Minimum Cut Problems Using Minimum Range Cut Algorithms.
Discret. Appl. Math., 1996

Variants for the Hough Transform for Line Detection.
Comput. Geom., 1996

Polynomial-Time Solutions to Image Segmentation.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

A Study of the LMT-Skeleton.
Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

Experimental Results of Randomized Clustering Algorithm.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
Finding k farthest pairs and k closest/farthest bichromatic pairs for points in the plane.
Int. J. Comput. Geom. Appl., 1995

On Minimum and Maximum Spanning Trees of Linearly Moving Points.
Discret. Comput. Geom., 1995

Optimal approximation of monotone curves on a grid.
Proceedings of the 7th Canadian Conference on Computational Geometry, 1995

1994
Efficient algorithms for minimum range cut problems.
Networks, 1994

Applications of Weighted Voronoi Diagrams and Randomization to Variance-Based <i>k</i>-Clustering (Extended Abstract).
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

1993
Graph endpoint coloring and distributed processing.
Networks, 1993

Efficient Algorithms for Finding the Most Vital Edge of a Minimum Spanning Tree.
Inf. Process. Lett., 1993

How to Treat Delete Requests in Semi-Online Problems.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Number Theory Helps Line Detection in Digital Images.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

1992
Optimal strategies for some team games.
Discret. Appl. Math., 1992

A Multiversion Cautious Scheduler with Dynamic Serialization Constraints for Database Concurrency Control.
Discret. Appl. Math., 1992

A fully polynomial time approximation scheme for minimum cost-reliability ratio problems.
Discret. Appl. Math., 1992

An e-approximation scheme for combinatorial optimization problems with minimum variance criterion.
Discret. Appl. Math., 1992

Finding <i>k</i> Farthest Pairs and <i>k</i> Closest/Farthest Bichromatic Pairs for Points in the Plane.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991
A two-commodity sharing problem on networks.
Networks, 1991

Finding k Points with Minimum Diameter and Related Problems.
J. Algorithms, 1991

Efficient Algorithms for the Minimum Range Cut Problem (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 1991

1990
Multiversion Cautious Schedulers for Database Concurrency Control.
IEEE Trans. Software Eng., 1990

Searching Minimax Game Trees under Memory Space Constraint.
Ann. Math. Artif. Intell., 1990

1989
A 1-Version Cautious Transaction Scheduler with Dynamic Version Selection.
Systems and Computers in Japan, 1989

Fining <i>k</i> Points with Minimum Spanning Trees and Related Problems.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988
Cautious Transaction Schedulers for Database Concurrency Control.
IEEE Trans. Software Eng., 1988

The Fair Resource Allocation Problem with Submodular Constraints.
Math. Oper. Res., 1988

Resource allocation problems - algorithmic approaches.
MIT Press series in the foundations of computing, MIT Press, ISBN: 978-0-262-09027-8, 1988

1987
Approximation algorithms for combinatorial fractional programming problems.
Math. Program., 1987

A parametric characterization and an ɛ-approximation scheme for the minimization of a quasiconcave program.
Discret. Appl. Math., 1987

A Cautious Scheduler for Multistep Transactions.
Algorithmica, 1987

1985
Cautious Transaction Schedulers with Admission Control.
ACM Trans. Database Syst., 1985

An Algorithm for the Equipollent Resource Allocation Problem.
Math. Oper. Res., 1985

An efficient algorithm for the parametric resource allocation problem.
Discret. Appl. Math., 1985

1983
On-Line Computation of Transitive Closures of Graphs.
Inf. Process. Lett., 1983

1982
An efficient algorithm for K shortest simple paths.
Networks, 1982

1981
An Algorithm for Finding K Minimum Spanning Trees.
SIAM J. Comput., 1981

An Algorithm for the K Best Solutions of the Resource Allocation Problem.
J. ACM, 1981


  Loading...