Asahi Takaoka

dblp:26/8975 · DBLP profile ↗
← Back
7ranked-venue papers
6as first author
3since 2021 · last 2024
0000-0002-0194-7138ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 6 · 5 first-author · 3 since 2021Software engineering, systems software and programming languages · 1 · 1 first-authorApplied, interdisciplinary, general and emerging computing · 1 · 1 first-author
YearPublicationVenuePosition
2024 A Characterization of Uniquely Representable Two-Directional Orthogonal Ray Graphs
Asahi Takaoka
COCOON (1)1
2024 Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
Asahi Takaoka
Discret. Appl. Math.1
2021 A recognition algorithm for adjusted interval digraphs
Asahi Takaoka
Discret. Appl. Math.1
2020 Recognizing simple-triangle graphs by restricted 2-chain subgraph cover
Asahi Takaoka
Discret. Appl. Math.1
2020 A recognition algorithm for simple-triangle graphs
Asahi Takaoka
Discret. Appl. Math.1
2016 On orthogonal ray trees
Irina Mustata, Kousuke Nishikawa, Asahi Takaoka, Satoshi Tayu, Shuichi Ueno
Discret. Appl. Math.3
2014 Weighted dominating sets and induced matchings in orthogonal ray graphs
abstract
An orthogonal ray graph is a graph such that for each vertex, there exists an axis-parallel rays (closed half-lines) in the plane, and two vertices are adjacent if and only if the corresponding rays intersect. A 2-directional orthogonal ray graph is an orthogonal ray graph such that the corresponding ray of each vertex is a rightward ray or a downward ray. We recently showed in [12] that the weighted dominating set problem can be solved in O(n4log n) time for vertex-weighted 2-directional orthogonal ray graphs by using a new parameter, boolean-width of graphs, where n is the number of vertices in a graph. We improve the result by showing an O(n3)-time algorithm to solve the problem, based on a direct dynamic programming approach. We also show that the weighted induced matching problem can be solved in O(m6) time for edge-weighted orthogonal ray graphs, where m is the number of edges in a graph, closing the gap posed in [12].
Asahi Takaoka, Satoshi Tayu, Shuichi Ueno
CoDIT1