89 Result(s)

Chapter and Conference Paper

Multi-winner Approval Voting with Grouped Voters

We consider the general case of approval-based committee elections, where some attributes divide the voters into diverse groups which vary in size. This scenario occurs in applications like the presidential el...

Yinghui Wen, Chunjiao Song, Aizhong Zhou… in Combinatorial Optimization and Applications (2024)

Chapter and Conference Paper

Colorful Graph Coloring

Given a simple graph G and a positive integer d, the Colorful Graph Coloring problem (CGC) asks for the minimum number of colors needed to color the “coloring elements” of G, such that for every “colorful elemen...

Zhongyi Zhang, Jiong Guo in Frontiers of Algorithmic Wisdom (2022)

Chapter and Conference Paper

Possible and Necessary Winner Problems in Iterative Elections with Multiple Rules

An iterative election eliminates some candidates in each round until the remaining candidates have the same score according to a given voting rule. Prominent iterative voting rules include Hare, Coombs, Baldwi...

Peihua Li, Jiong Guo in Frontiers of Algorithmic Wisdom (2022)

Article

Sorting a Permutation by Best Short Swaps

A permutation is happy, if it can be transformed into the identity permutation using as many short swaps as one third times the number of inversions in the permutation. The complexity of the decision version of s...

Shu Zhang, Daming Zhu, Haitao Jiang, Jiong Guo, Haodi Feng, **aowen Liu in Algorithmica (2021)

Chapter and Conference Paper

Constrained Stable Marriage with Free Edges or Few Blocking Pairs

Given two disjoint sets U and W, where the members (also called agents) of U and W are called men and women, respectively, and each agent is associated with an ordered preference list that ranks a subset of the a...

Yinghui Wen, Jiong Guo in Combinatorial Optimization and Applications (2021)

Article

Parameterized Complexity of Voter Control in Multi-Peaked Elections

We study the parameterized complexity of voter control problems in κ-peaked elections, where κ is a positive integer. In particular, we focus on the constructive/destructive control by adding/deleting votes for C...

Yongjie Yang, Jiong Guo in Theory of Computing Systems (2018)

Article

Possible winner problems on partial tournaments: a parameterized study

We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D ...

Yongjie Yang, Jiong Guo in Journal of Combinatorial Optimization (2017)

Chapter and Conference Paper

A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction

This paper investigates the problem of maximum stacking base pairs from RNA secondary structure prediction. The basic version of maximum stacking base pairs problem as: given an RNA sequence, to find a maximum...

Aizhong Zhou, Haitao Jiang, Jiong Guo… in Combinatorial Optimization and Applications (2017)

Chapter and Conference Paper

Improved Approximation Algorithm for the Maximum Base Pair Stackings Problem in RNA Secondary Structures Prediction

We investigate the maximum base pair stackings problem from RNA Secondary Structures prediction in this paper. Previously, Ieong et al. defined a basic version of this maximum base pair stackings problem as: give...

Aizhong Zhou, Haitao Jiang, Jiong Guo, Haodi Feng, Nan Liu… in Computing and Combinatorics (2017)

Reference Work Entry In depth

Undirected Feedback Vertex Set

Jiong Guo in Encyclopedia of Algorithms (2016)

Chapter and Conference Paper

Kernelization of Two Path Searching Problems on Split Graphs

In the k-Vertex-Disjoint Paths problem, we are given a graph G and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the

Yongjie Yang, Yash Raj Shrestha, Wenjun Li, Jiong Guo in Frontiers in Algorithmics (2016)

Article

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments

The k-feedback arc set problem is to determine whether there is a set F of at most k arcs in a directed graph G such that the removal of F makes G acyclic. The k-feedback arc set problems in tournaments and bipar...

Mingyu **ao, Jiong Guo in Algorithmica (2015)

Chapter and Conference Paper

Design Tutoring Feedback to Increase Online Learners’ Satisfaction

Online learners’ persistence and high dropout rate is a crucial problem in online learning context. Online learners’ satisfaction is a major factor affecting persistence. How to design feedback strategies to p...

Yuhui Ma, Ronghuai Huang, **aoying Zhang, Jiong Guo in Emerging Issues in Smart Learning (2015)

Article

Covering tree with stars

We study the tree edit distance (TED) problem with edge deletions and edge insertions as edit operations. We reformulate a special case of this problem as Covering Tree with Stars (CTS): given a tree T and a set

Jan Baumbach, Jiong Guo, Rashid Ibragimov in Journal of Combinatorial Optimization (2015)