BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Hiroshi Nagamochi

Hiroshi Nagamochi contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsComputational Engineering, Finance, and Sciencemath.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2022arXiv

Polynomial-delay Enumeration Algorithms in Set Systems

We consider a set system $(V, {\mathcal C}\subseteq 2^V)$ on a finite set $V$ of elements, where we call a set $C\in {\mathcal C}$ a component. We assume that two oracles $\mathrm{L}_1$ and $\mathrm{L}_2$ are available, where given two subsets $X,Y\subseteq V$, $\mathrm{L}_1$ returns a maximal component $C\in {\mathcal C}$ with $X\subseteq C\subseteq Y$; and given a set $Y\subseteq V$, $\mathrm{L}_2$ returns all maximal components $C\in {\mathcal C}$ with $C\subseteq Y$. Given a set $I$ of attributes and a function $σ:V\to 2^I$ in a transitive system, a component $C\in {\mathcal C}$ is called a solution if the set of common attributes in $C$ is inclusively maximal; i.e., $\bigcap_{v\in C}σ(v)\supsetneq \bigcap_{v\in X}σ(v)$ for any component $X\in{\mathcal C}$ with $C\subsetneq X$. We prove that there exists an algorithm of enumerating all solutions (or all components) in delay bounded by a polynomial with respect to the input size and the running times of the oracles.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Novel Method for Inference of Acyclic Chemical Compounds with Bounded Branch-height Based on Artificial Neural Networks and Integer Programming

Analysis of chemical graphs is a major research topic in computational molecular biology due to its potential applications to drug design. One approach is inverse quantitative structure activity/property relationship (inverse QSAR/QSPR) analysis, which is to infer chemical structures from given chemical activities/properties. Recently, a framework has been proposed for inverse QSAR/QSPR using artificial neural networks (ANN) and mixed integer linear programming (MILP). This method consists of a prediction phase and an inverse prediction phase. In the first phase, a feature vector $f(G)$ of a chemical graph $G$ is introduced and a prediction function $ψ$ on a chemical property $π$ is constructed with an ANN. In the second phase, given a target value $y^*$ of property $π$, a feature vector $x^*$ is inferred by solving an MILP formulated from the trained ANN so that $ψ(x^*)$ is close to $y^*$ and then a set of chemical structures $G^*$ such that $f(G^*)= x^*$ is enumerated by a graph search algorithm. The framework has been applied to the case of chemical compounds with cycle index up to 2. The computational results conducted on instances with $n$ non-hydrogen atoms show that a feature vector $x^*$ can be inferred for up to around $n=40$ whereas graphs $G^*$ can be enumerated for up to $n=15$. When applied to the case of chemical acyclic graphs, the maximum computable diameter of $G^*$ was around up to around 8. We introduce a new characterization of graph structure, "branch-height," based on which an MILP formulation and a graph search algorithm are designed for chemical acyclic graphs. The results of computational experiments using properties such as octanol/water partition coefficient, boiling point and heat of combustion suggest that the proposed method can infer chemical acyclic graphs $G^*$ with $n=50$ and diameter 30.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Design of Polynomial-delay Enumeration Algorithms in Transitive Systems

In this paper, as a new notion, we define a transitive system to be a set system $(V, {\mathcal C}\subseteq 2^V)$ on a finite set $V$ of elements such that every three sets $X,Y,Z\in{\mathcal C}$ with $Z\subseteq X\cap Y$ implies $X\cup Y\in{\mathcal C}$, where we call a set $C\in {\mathcal C}$ a component. We assume that two oracles $\mathrm{L}_1$ and $\mathrm{L}_2$ are available, where given two subsets $X,Y\subseteq V$, $\mathrm{L}_1$ returns a maximal component $C\in {\mathcal C}$ with $X\subseteq C\subseteq Y$; and given a set $Y\subseteq V$, $\mathrm{L}_2$ returns all maximal components $C\in {\mathcal C}$ with $C\subseteq Y$. Given a set $I$ of attributes and a function $σ:V\to 2^I$ in a transitive system, a component $C\in {\mathcal C}$ is called a solution if the set of common attributes in $C$ is inclusively maximal; i.e., $\bigcap_{v\in C}σ(v)\supsetneq \bigcap_{v\in X}σ(v)$ for any component $X\in{\mathcal C}$ with $C\subsetneq X$. We prove that there exists an algorithm of enumerating all solutions in delay bounded by a polynomial with respect to the input size and the running times of the oracles. The proposed algorithm yields the first polynomial-delay algorithms for enumerating connectors in an attributed graph and for enumerating all subgraphs with various types of connectivities such as all $k$-edge/vertex-connected induced subgraphs and all $k$-edge/vertex-connected spanning subgraphs in a given undirected/directed graph for a fixed $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Enumerating Chemical Graphs with Mono-block 2-Augmented Tree Structure from Given Upper and Lower Bounds on Path Frequencies

We consider a problem of enumerating chemical graphs from given constraints concerning their structures, which has an important application to a novel method for the inverse QSAR/QSPR recently proposed. In this paper, the structure of a chemical graph is specified by a feature vector each of whose entries represents the frequency of a prescribed path. We call a graph a 2-augmented tree if it is obtained from a tree (an acyclic graph) by adding edges between two pairs of nonadjacent vertices. Given a set of feature vectors as the interval between upper and lower bounds of feature vectors, we design an efficient algorithm for enumerating chemical 2-augmented trees that satisfy the path frequency specified by some feature vector in the set. We implemented the proposed algorithm and conducted some computational experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Enumerating Chemical Graphs with Two Disjoint Cycles Satisfying Given Path Frequency Specifications

Enumerating chemical graphs satisfying given constraints is a fundamental problem in mathematical and computational chemistry, and plays an essential part in a recently proposed framework for the inverse QSAR/QSPR. In this paper, constraints are given by feature vectors each of which consists of the frequencies of paths in a given set of paths. We consider the problem of enumerating chemical graphs that satisfy the path frequency constraints, which are given by a pair of feature vectors specifying upper and lower bounds of the frequency of each path. We design a branch-and-bound algorithm for enumerating chemical graphs of bi-block 2-augmented structure, that is, graphs that contain two edge-disjoint cycles. We present some computational experiments with an implementation of our proposed algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Characterizing Star-PCGs

A graph $G$ is called a pairwise compatibility graph (PCG, for short) if it admits a tuple $(T,w, d_{\min},d_{\max})$ of a tree $T$ whose leaf set is equal to the vertex set of $G$, a non-negative edge weight $w$, and two non-negative reals $d_{\min}\leq d_{\max}$ such that $G$ has an edge between two vertices $u,v\in V$ if and only if the distance between the two leaves $u$ and $v$ in the weighted tree $(T,w)$ is in the interval $[d_{\min}, d_{\max}]$. The tree $T$ is also called a witness tree of the PCG $G$. The problem of testing if a given graph is a PCG is not known to be NP-hard yet. To obtain a complete characterization of PCGs is a wide open problem in computational biology and graph theory. In literature, most witness trees admitted by known PCGs are stars and caterpillars. In this paper, we give a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Some Reduction Operations to Pairwise Compatibility Graphs

A graph $G=(V,E)$ with a vertex set $V$ and an edge set $E$ is called a pairwise compatibility graph (PCG, for short) if there are a tree $T$ whose leaf set is $V$, a non-negative edge weight $w$ in $T$, and two non-negative reals $d_{\min}\leq d_{\max}$ such that $G$ has an edge $uv\in E$ if and only if the distance between $u$ and $v$ in the weighted tree $(T,w)$ is in the interval $[d_{\min}, d_{\max}]$. PCG is a new graph class motivated from bioinformatics. In this paper, we give some necessary and sufficient conditions for PCG based on cut-vertices and twins, which provide reductions among PCGs. Our results imply that complete $k$-partite graph, cactus, and some other graph classes are subsets of PCG.

0 citations0 reviewsNo code linkedOpen access