143 citations · 198 across the 19 of their papers we have counts for
10 papers · 1 filter
Bounded-Degree Cut is Fixed-Parameter Tractable
Mingyu Xiao, Hiroshi Nagamochi
In the bounded-degree cut problem, we are given a multigraph , two disjoint vertex subsets , two functions $\mathrm{u}_A, \mathrm{u}_B:V\to \{0,1,\ldots,|E…
A Novel Method for Inference of Acyclic Chemical Compounds with Bounded Branch-height Based on Artificial Neural Networks and Integer Programming
Naveed Ahmed Azam, Jianshen Zhu, Yanming Sun +5
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 stru…
Enumerating Chemical Graphs with Two Disjoint Cycles Satisfying Given Path Frequency Specifications
Kyousuke Yamashita, Ryuji Masui, Xiang Zhou +4
Enumerating chemical graphs satisfying given constraints is a fundamental problem in mathematical and computational chemistry, and plays an essential part in a recently proposed fr…
Enumerating Chemical Graphs with Mono-block 2-Augmented Tree Structure from Given Upper and Lower Bounds on Path Frequencies
Yuui Tamura, Yuhei Nishiyama, Chenxi Wang +4
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/Q…
Characterizing Star-PCGs
Mingyu Xiao, Hiroshi Nagamochi
A graph is called a pairwise compatibility graph (PCG, for short) if it admits a tuple of a tree whose leaf set is equal to the vertex set of …
Some Reduction Operations to Pairwise Compatibility Graphs
Mingyu Xiao, Hiroshi Nagamochi
A graph with a vertex set and an edge set is called a pairwise compatibility graph (PCG, for short) if there are a tree whose leaf set is , a non-negative…
A Linear-time Algorithm for Integral Multiterminal Flows in Trees
Mingyu Xiao, Hiroshi Nagamochi
In this paper, we study the problem of finding an integral multiflow which maximizes the sum of flow values between every two terminals in an undirected tree with a nonnegative int…
Exact Algorithms for Dominating Induced Matching Based on Graph Partition
Mingyu Xiao, Hiroshi Nagamochi
A dominating induced matching, also called an efficient edge domination, of a graph with vertices and edges is a subset of edges in the gr…
Exact Algorithms for Maximum Independent Set
Mingyu Xiao, Hiroshi Nagamochi
We show that the maximum independent set problem (MIS) on an -vertex graph can be solved in time and polynomial space, which even is faster than Robson's $1.2…
An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure
Mingyu Xiao, Hiroshi Nagamochi
The paper presents an O^*(1.2312^n)-time and polynomial-space algorithm for the traveling salesman problem in an n-vertex graph with maximum degree 3. This improves the previous ti…