B. Sheng

activity

20142022

most citedParameterized Complexity of the

k

-Arc Chinese Postman Problem

7 citations · 20 across the 13 of their papers we have counts for

collaborators

Showing 2015Show all

2 papers · 1 filter

cs.DS2015★ 2 cited

Chinese Postman Problem on Edge-Colored Multigraphs

Gregory Gutin, Mark Jones, Bin Sheng +2

It is well-known that the Chinese postman problem on undirected and directed graphs is polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in…

cs.DS2015

Linear-Vertex Kernel for the Problem of Packing $r$ -Stars into a Graph without Long Induced Paths

Florian Barbero, Gregory Gutin, Mark Jones +2

Let integers $r \geq 2$ and $d \geq 3$ be fixed. Let $G_{d}$ be the set of graphs with no induced path on $d$ vertices. We study the problem of packing $k$ vertex-disjoint copies…

Chinese Postman Problem on Edge-Colored Multigraphs

Linear-Vertex Kernel for the Problem of Packing r-Stars into a Graph without Long Induced Paths

Linear-Vertex Kernel for the Problem of Packing $r$ -Stars into a Graph without Long Induced Paths