43 Result(s)
within
Chapter
Minghui **ao
Algorithm Analysis and Problem Complexity
Discrete Mathematics in Computer Science
-
Chapter and Conference Paper
Sequent Calculi for Normal Update Logics
Normal update logic is the temporalization of normal conditional logic. Sequent calculi for the least normal update logic $$\mathbf {U...
-
Chapter and Conference Paper
Edge-Disjoint Packing of Stars and Cycles
We study the parameterized complexity of two graph packing problems, Edge-Disjoint \(k\) ...
-
Chapter and Conference Paper
Trees, Paths, Stars, Caterpillars and Spiders
For any \(k \ge 2\) k ≥ ...
-
Chapter and Conference Paper
Quell
We study the computational complexity of the puzzle Quell. The goal is to collect pearls by sliding a droplet of water over them in a grid map. The map contains obstacles. In each move, the droplet slides in o...
-
Chapter and Conference Paper
Shortest Color-Spanning Intervals
Given a set of n points on a line, where each point has one of k colors, and given an integer s i ≥ 1 for each color i, 1 ≤ i ≤ k, the problem Shortest Color-Sp...
-
Chapter and Conference Paper
Competitive Algorithms for Unbounded One-Way Trading
In the one-way trading problem, a seller has some product to be sold to a sequence σ of buyers u 1, u 2, …, u σ arriving online ...
-
Chapter and Conference Paper
On Covering Points with Minimum Turns
We point out mistakes in several previous FPT algorithms for k -Link Covering Tour and its variants in ℝ2, and show that the previous NP-hardness proofs for Minimum-Link Rectilinear Covering Tour an...
-
Chapter and Conference Paper
Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science with extensive applications in diverse areas ranging from spelling error corrections to molecular biology....
-
Chapter and Conference Paper
Maximal Empty Boxes Amidst Random Points
We show that the expected number of maximal empty axis-parallel boxes amidst n random points in the unit hypercube [0,1] d in ℝ d is ...
-
Chapter and Conference Paper
Parameterized Complexity in Multiple-Interval Graphs: Domination
We show that several variants of the problem k -Dominating Set, including k -Connected Dominating Set, k -Independent Dominating Set, k -Dominating Clique,
-
Chapter and Conference Paper
H ∞ Synchronization Control in Nonlinear Time-Delay Complex Dynamical Network
On the basis of Lyapunov stability theory and LMI technique, this paper investigates H ∞ synchronization control of time-varying synchronization state in general complex networks with time-delay...
-
Chapter and Conference Paper
Flip** Triangles and Rectangles
We study the chromatic number of the flip graph of triangles determined by n points in convex position in the plane, and present new or improved bounds on several related parameters for this graph. We also find t...
-
Chapter and Conference Paper
Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy
We present new results on the parameterized complexities of k - Vertex Clique Partition and k -Separating Vertices in multiple-interval graphs and their complements, and present a very...
-
Chapter and Conference Paper
Opaque Sets
The problem of finding “small” sets that meet every straight-line which intersects a given convex region was initiated by Mazurkiewicz in 1916. We call such a set an opaque set or a barrier for that region. We co...
-
Chapter and Conference Paper
Minimum-Perimeter Intersecting Polygons
Given a set \({\mathcal S}\) of segments in the plane, a polygon P is an intersecting polygon of
-
Chapter and Conference Paper
Inapproximability of Maximal Strip Recovery: II
Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given d genomic maps...
-
Chapter and Conference Paper
Recognizing d-Interval Graphs and d-Track Interval Graphs
A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizatio...
-
Chapter and Conference Paper
Approximability of Constrained LCS
The problem Constrained Longest Common Subsequence is a natural extension to the classical problem Longest Common Subsequence, and has important applications to bioinformatics. Given k input sequences A ...
-
Chapter and Conference Paper
On Reconfiguration of Disks in the Plane and Related Problems
We revisit two natural reconfiguration models for systems of disjoint objects in the plane: translation and sliding. Consider a set of n pairwise interior-disjoint objects in the plane that need to be brought fro...
-
Chapter and Conference Paper
A Modified Projection Neural Network for Linear Variational Inequalities and Quadratic Optimization Problems
Variational inequalities provide us with a tool to study a wide class of optimization arising in pure and applied sciences. In the paper,we present a neural network for solving linear variational inequalities ...
