Search

Your search keyword '"Naomi Nishimura"' showing total 193 results
Start Over Author "Naomi Nishimura"
193 results on '"Naomi Nishimura"'

1. Introduction to Reconfiguration

Author

Naomi Nishimura

Subjects
reconfiguration problems, algorithms, complexity, Industrial engineering. Management engineering, T55.4-60.8, Electronic computers. Computer science, QA75.5-76.95
Abstract

Reconfiguration is concerned with relationships among solutions to a problem instance, where the reconfiguration of one solution to another is a sequence of steps such that each step produces an intermediate feasible solution. The solution space can be represented as a reconfiguration graph, where two vertices representing solutions are adjacent if one can be formed from the other in a single step. Work in the area encompasses both structural questions (Is the reconfiguration graph connected?) and algorithmic ones (How can one find the shortest sequence of steps between two solutions?) This survey discusses techniques, results, and future directions in the area.

Published
2018
Full Text
View/download PDF

2. Vertex Cover Reconfiguration and Beyond

Author

Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, and Sebastian Siebertz

Subjects
reconfiguration, vertex cover, solution space, fixed-parameter tractability, bipartite graphs, Industrial engineering. Management engineering, T55.4-60.8, Electronic computers. Computer science, QA75.5-76.95
Abstract

In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ℓ and two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at most ℓ vertex additions or removals such that every operation results in a vertex cover of size at most k. Motivated by results establishing the W [ 1 ] -hardness of VCR when parameterized by ℓ, we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains W [ 1 ] -hard on bipartite graphs, is NP -hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs.

Published
2018
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results