Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Tian Liu 0001

dblp:49/4426-1 · DBLP profile ↗
← Back
20ranked-venue papers
5as first author
0since 2021 · last 2017
0000-0001-8313-8037ORCID · conflict

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 10 · 2 first-authorArtificial intelligence and machine learning · 8 · 1 first-authorApplied, interdisciplinary, general and emerging computing · 2 · 2 first-authorGraphics, computer vision, multimedia, augmented reality and games · 1 · 1 first-author

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Combinatorics and discrete mathematics · 100%

Topics — the 2 heaviest of 2, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Combinatorics and discrete mathematics
hypergraph
0.112011
Large Hinge Width on Sparse Random Hypergraphs · IJCAI 2011
Combinatorics and discrete mathematics › probabilistic combinatorics
random hypergraphs
0.112011
Large Hinge Width on Sparse Random Hypergraphs · IJCAI 2011

Methods — techniques the papers use, named apart from their topics

probabilistic analysis · 0.1
YearPublicationVenuePosition
2017 A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
abstract
The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition (MCSP) problem, both of which have applications in many fields including text compression and bioinformatics. k-Max-Duo is the restricted version of Max-Duo, where every letter of the alphabet occurs at most k times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree \Delta \le 6(k-1). In particular, 2-Max-Duo can then be approximated arbitrarily close to 1.8 using the state-of-the-art approximation algorithm for the MIS problem. 2-Max-Duo was proved APX-hard and very recently a (1.6 + \epsilon)-approximation was claimed, for any \epsilon > 0. In this paper, we present a vertex-degree reduction technique, based on which, we show that 2-Max-Duo can be approximated arbitrarily close to 1.4.
Yong Chen 0002, Guohui Lin, Tian Liu 0001, Taibo Luo, Peng Zhang 0008
ISAAC4
2015 Improved parameterized and exact algorithms for cut problems on trees
Iyad Kanj, Guohui Lin, Tian Liu 0001, Weitian Tong, Ge Xia, Jinhui Xu 0001, Boting Yang, Peng Zhang 0008, Binhai Zhu
Theor. Comput. Sci.3
2014 Restricted Bipartite Graphs: Comparison and Hardness Results
Tian Liu 0001
AAIM1
2014 Algorithms for Cut Problems on Trees
Iyad Kanj, Guohui Lin, Tian Liu 0001, Weitian Tong, Ge Xia, Jinhui Xu 0001, Boting Yang, Peng Zhang 0008, Binhai Zhu
COCOA3
2014 Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems
Min Lu 0004, Tian Liu 0001, Weitian Tong, Guohui Lin, Ke Xu 0001
TAMC2
2014 Circular convex bipartite graphs: Feedback vertex sets
Tian Liu 0001, Min Lu 0004, Ke Xu 0001
Theor. Comput. Sci.1
2014 Approximating the maximum multiple RNA interaction problem
Weitian Tong, Randy Goebel, Tian Liu 0001, Guohui Lin
Theor. Comput. Sci.3
2013 Circular Convex Bipartite Graphs: Feedback Vertex Set
Min Lu 0004, Tian Liu 0001, Ke Xu 0001
COCOA3
2013 Approximation Algorithms for the Maximum Multiple RNA Interaction Problem
Weitian Tong, Randy Goebel, Tian Liu 0001, Guohui Lin
COCOA3
2013 Tractable Connected Domination for Restricted Bipartite Graphs (Extended Abstract)
Tian Liu 0001, Ke Xu 0001
COCOON2
2013 Feedback vertex sets on restricted bipartite graphs
Tian Liu 0001, Ke Xu 0001
Theor. Comput. Sci.2
2012 Feedback Vertex Sets on Tree Convex Bipartite Graphs
Tian Liu 0001, Ke Xu 0001
COCOA2
2011 On Unique Games with Negative Weights
Peng Cui 0008, Tian Liu 0001, Ke Xu 0001
COCOA2
2011 Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
Tian Liu 0001, Ke Xu 0001
COCOA2
2011 A Note on Treewidth in Random Graphs
Tian Liu 0001, Peng Cui 0008, Ke Xu 0001
COCOA2
2011 Large Hinge Width on Sparse Random Hypergraphs
Tian Liu 0001, Xiaxiang Lin, Kaile Su, Ke Xu 0001
IJCAI1
2010 On exponential time lower bound of Knapsack under backtracking
Xin Li 0051, Tian Liu 0001
Theor. Comput. Sci.2
2007 Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model
Xin Li 0051, Tian Liu 0001, Liyan Qian, Jin Xu 0002, Ke Xu 0001
TAMC2
2000 A Note on Closeness between NP-Hard Sets and C=P
Tian Liu 0001
J. Comput. Sci. Technol.1
2000 Some Structural Properties of SAT
Tian Liu 0001
J. Comput. Sci. Technol.1