Source author record

Shungo Koichi

Shungo Koichi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO math.MG

Catalog footprint

What is connected

2works

2topics

1close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

preprint2011arXiv

On duality and fractionality of multicommodity flows in directed networks

In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight $μ$, we define a metrized polyhedral complex, called the directed tight span $T_μ$, and prove that the dual of $μ$-weighted maximum multiflow problem reduces to a facility location problem on $T_μ$. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by $μ$. By utilizing this duality, we establish the classifications of terminal weights admitting combinatorial min-max relation (i) for every network and (ii) for every Eulerian network. Our result includes Lomonosov-Frank theorem for directed free multiflows and Ibaraki-Karzanov-Nagamochi's directed multiflow locking theorem as special cases.

preprint2010arXiv

On tight spans and tropical polytopes for directed distances

An extension $(V,d)$ of a metric space $(S,μ)$ is a metric space with $S \subseteq V$ and $d|_S = μ$, and is said to be tight if there is no other extension $(V,d')$ of $(S,μ)$ with $d' \leq d$. Isbell and Dress independently found that every tight extension is isometrically embedded into a certain metrized polyhedral complex associated with $(S,μ)$, called the tight span. This paper develops an analogous theory for directed metrics, which are "not necessarily symmetric" distance functions satisfying the triangle inequality. We introduce a directed version of the tight span and show that it has such a universal embedding property for tight extensions. Also we newly introduce another natural class of extensions, called cyclically tight extensions, and show that (a fiber of) the tropical polytope, introduced by Develin and Sturmfels, has a universal embedding property for cyclically tight extensions. As an application, we prove the following directed version of tree metric theorem: directed metric $μ$ is a directed tree metric if and only if the tropical rank of $-μ$ is at most two. Also we describe how tight spans and tropical polytopes are applied to the study in multicommodity flows in directed networks.