GTCO 2011 - Workshop on Graph Theory and Combinatorial Optimization
Shanghai·China
October 29-31, 2011
Sponsored by Department of Mathematics, Shanghai University
Open Laboratory for Operations Research & Optimization
Shanghai Operations Research Society
Supportedby The Key Disciplines of Shanghai Municipality-Operations Research and Cybernetics
1
GTCO 2011 - Workshop on Graph Theory and Combinatorial Optimization
Workshop Organising Committee:
Chairman: Qingwen Wang (ShanghaiUniversity)
Co-Chair: Liying Kang (ShanghaiUniversity)
Members: Yanqin Bai (ShanghaiUniversity)
Xiaomei Jia (ShanghaiUniversity), Erfang Shan (ShanghaiUniversity)
Xiying Yuan (ShanghaiUniversity), Weiya Zhong (ShanghaiUniversity)
Xiaoxia Wang (ShanghaiUniversity)
Wenhuan Wang (ShanghaiUniversity)
Prabhu Manyem (ShanghaiUniversity)
Yongjian Yang (ShanghaiUniversity)
Xiwen Lu (EastChinaUniversity of Science and TechnologyShanghai Operational Research Society)
Zhaohui Liu (EastChinaUniversity of Science and TechnologyShanghai Operational Research Society)
Organizers:
Department of Mathematics, Shanghai University
Shanghai Operations Research Society
Website:
1
Programme of
GTCO 2011 - Workshop on Graph Theory and Combinatorial Optimization
October 29-31, 2011
ShanghaiUniversity
October 29, 2011 (Saturday)
Time / Place: Lecture Hall of Lehu Building 乐乎新楼报告厅7:00---8:00 / Breakfast: Dining Room ofLehu Building乐乎新楼餐厅
8:30---9:00 / Opening Ceremony
9:00---9:10 / Photo
October 29,2011 (Saturday)
PlenaryTalk
Time / Place: Lecture Hall of Lehu Building乐乎新楼报告厅Speaker/Title / Chairman
9:10---10:00 / Nick Wormald
University of Waterloo, Canada
Cops and Robber on a Random Graph / Yusheng Li
10:00---10:20 / Tea Break
10:20---11:10 / Ding-Zhu Du
University of Texas at Dallas, USA
Routing Cost Constrained Connected Dominating Sets / Xiaodong Hu
11:10--12:00 /
Xuding Zhu
Zhejiang Normal University
Some Problems on Circular Colouring of Graphs12:00-13:30 / Lunch: Dining Room ofLehu Building乐乎新楼餐厅
October 29,2011 (Saturday)
SectionTalk
Time / Section Talk A:Lecture Hall of Lehu Building乐乎新楼报告厅 / Section Talk B: Room 507, Building GSpeaker/Title / Chairman / Speaker/Title / Chairman
13:30---14:00 / Xiaodong Hu
Academy of Mathematics and Systems Science, ChineseAcademy of Sciences
Improving Performances of Selfish RingRouting via Limited Cooperations / An Chang / Guochuan Zhang
ZhejiangUniversity
Approximation Algorithms for a Bi-level Knapsack Problem / Xiwen Lu
14:00---14:30 / Yusheng Li
TongjiUniversity
Remarks for the Local Lemma / Guochun Tang
ShanghaiSecondPolytechnicUniversity
A Revised Proof of the Optimality for the Kise–Ibaraki–Mine Algorithm
14:30---15:00 / Jianliang Wu
ShandongUniversity
Total Coloring of Planar GraphsWithout Intersecting Short Cycles / Zhiyi Tan
ZhejiangUniversity
Scheduling with Machine Maintenance for Minsum Criteria
15:00---15:30 /
Weifan Wang
Zhejiang Normal University
The Surviving Rate of a Planar Graph / Hong ZhuEastChinaNormalUniversity
Arithmetic Operations Over Regular Languages
October 29,2011 (Saturday)
SectionTalk
15:30--15:50 / Tea BreakTime / Section Talk A:Lecture Hall of Lehu Building乐乎新楼报告厅 / Section Talk B: Room 507, Building G
Speaker/Title / Chairman / Speaker/Title / Chairman
15:50---16:20 / Liming Xiong
Beijing Institute of Technology
An Extension of the Chvάtal-Erdös Theorem:Counting the Number of Maximum Independent Sets / Jianliang Wu / Xujin Chen
Academy of Mathematics and Systems Science, ChineseAcademy of Sciences
Bonds with Parity Cons Traints / Weiya Zhong
16:20---16:50 / Zhiquan Hu
CentralChinaNormalUniversity
A Lower Bound of Circumferences Involving Connectivities and Independence Numbers of Subgraphs / Xiaoguang Bao
EastChinaUniversity of Science and Technology
Improved Approximation Algorithms for the Clustered Traveling Salesman Problem
16:50---17:20 / Yuehua Bu
College of Mathematics Physics and Information Technology, ZhejiangNormalUniversity
BB-coloring of Planar Graphs / Kejun Zhao
EastChinaUniversity of Science and Technology
Fully Polynomial Approximation Schemes for Two-agent Scheduling on Parallel Machines
18:00 / Banquet: Xuanleshi Hotel轩乐诗大酒店
October 30,2011 (Sunday)
Plenary Talk
Time / Place: Lecture Hall of Lehu Building 乐乎新楼报告厅7:00---8:00 / Breakfast: Dining Room ofLehu Building乐乎新楼餐厅
Speaker/Title / Chairman
8:30---9:20 / Zhicheng Gao
University of Macao CarletonUniversity
Asymptotic Properties of Locally Restricted Compositions / Weifan Wang
9:20---10:10 / Beifang Chen
HongKongUniversity of Science and Technology
Tutte Type Polynomials From Viewpoint of Homology and Cohomology
10:10---10:30 / Tea Break
October 30,2011 (Sunday)
Section Talk
Time / Place: Lecture Hall of Lehu Building 乐乎新楼报告厅Speaker/Title / Chairman
10:30---11:00 / Michel Habib
University Paris Diderot - Paris7, France
Algorithms for Some -join Decompositions of Graphs / Lianzhu Zhang
11:00---11:30 / Yaokun Wu
ShanghaiJiaoTongUniversity
A -sweep LBFS Certifying Algorithm for Recognizing Interval Graphs
11:30---12:00 / Min Xu
BeijingNormalUniversity
On the Restricted Forwarding Index Problem in Communication Networks
12:00---13:30 / Lunch:Dining Room ofLehu Building乐乎新楼餐厅
October 30,2011 (Sunday)
Plenary Talk
Time / Place: Room 507, Building G / ChairmanSpeaker/Title
13:30---14:20 / Sanming Zhou
University of Melbourne, Australia
Symmetric Graphs and Transitive Block Designs / Changhong Lu
Section Talk
Time / Place: Room 507, Building G / ChairmanSpeaker/Title
14:20---14:50 / Jiming GuoChinaUniversity of Petroleum
On the Laplacian Spectral Radius of Graphs / Huiqing Liu
14:50---15:20 / Changhong Lu
EastChinaNormalUniversity
Identifying Codes and Locating-dominating Sets on Paths and Cycles
15:20--15:40 / Tea BreakOctober 30,2011 (Sunday)
Section Talk
Time /Place: Room 507, Building G
/ ChairmanSpeaker/Title
15:40---16:10 / Lianzhu ZhangXiamen University
Pfaffian Graphs Embedding on the Torus / Xiaodong Zhang
16:10---16:40 / Yijia Chen
ShanghaiJiaoTongUniversity
The Parameterized Complexity of K-edge Induced Subgraphs
16:40---17:10 / Yuqin Sun
Shanghai University of Electric Power
A Bound for Size Ramsey Numbers of Multi-partite Graphs
17:30 / Pujiang night tour（Including dinner） 浦江夜游(含晚餐)
Note: For those who join Pujiang night tour，please gather in front of Lehu Building at 5:30 PM. For those who do not join Pujiang night tour，you may
have dinner in the dining room ofLehuBuilding.
友情提示：参加浦江夜游的来宾请在下午5：30于乐乎楼门前集合。不参加浦江夜游的来宾可以在乐乎新楼餐厅享用我们提供的套餐。
October 31,2011 (Monday)
Section Talk
Time / Place: Lecture Hall of Lehu Building乐乎新楼报告厅7:00---8:00 / Breakfast: Dining Room ofLehu Building乐乎新楼餐厅
Speaker/Title / Chairman
8:30---9:00 / Moo YoungSohn
Changwon National University, Korea
Bondage Number of the Graph BundleHaving Reflection Voltage Assignment / Maocheng Cai
9:00---9:30 / Hye Kyung Kim
Catholic University of Deagu, Korea
Note on Paired-domination Games
9:30---10:00 / Han Ren
East China Normal University
Finding More Short Cycles in (Embedded)Graphs
10:00---10:20 / Tea Break
October 31,2011 (Monday)
Section Talk
Time / Place: Lecture Hall of Lehu Building乐乎新楼报告厅Speaker/Title / Chairman
10:20---10:50 / Huiqing Liu
HubeiUniversity
Fault-tolerant Maximal Local-connectivity on Bubblesort Star Graphs / Prabhu Manyem
10:50---11:20 / Yanmei Hong
ShanghaiUniversity
Non-separating Cycles Avoiding Specific Vertices
11:20---11:50 / Xiumei Wang
ZhengzhouUniversity
Characterizations of PM-compact Bipartite and Near-bipartite Graphs
12:00---13:30 / Lunch:Dining Room ofLehu Building乐乎新楼餐厅
1
Contents
Plenary Talks
Nick Wormald, Cops and Robber on a Random Graph...... 1
Ding-Zhu Du, Routing Cost Constrained Connected Dominating Sets...... 2
Xuding Zhu, Some Problems on Circular Colouring of Graphs...... 3
Zhicheng Gao, Asymptotic Properties of Locally Restricted Compositions...... 4
Beifang Chen, Tutte Type Polynomials From Viewpoint of Homology and Cohomology...... 5
Sanming Zhou, Symmetric Graphs and Transitive Block Designs...... 6
Invited Talks
Xiaodong Hu, Improving Performances of Selfish Ring Routing via Limited Cooperations
Guochuan Zhang, Approximation Algorithms for a Bi-level Knapsack Problem
Yusheng Li,Remarks for the Local Lemma
Guochun Tang, A Revised Proof of the Optimality for the Kise–Ibaraki–Mine Algorithm
Jianliang Wu, Total Coloring of Planar GraphsWithout Intersecting Short Cycles...... 9
Zhiyi Tan, Scheduling with Machine Maintenance for Minsum Criteria
Weifan Wang, The Surviving Rate of a Planar Graph
Hong Zhu, Arithmetic Operations over Regular Languages
Liming Xiong, An Extension of the Chvάtal-Erdös Theorem: Counting the Number of Maximum Independent Sets
Xujin Chen, Bonds with Parity Constraints
Zhiquan Hu, A Lower Bound of Circumferences Involving Connectivities and Independence Numbers of Subgraphs
Xiaoguang Bao, Improved Approximation Algorithms for the Clustered Traveling Salesman Problem
Yuehua Bu, BB-coloring of Planar Graphs
Kejun Zhao, Fully Polynomial Approximation Schemes for Two-agent Scheduling on Parallel Machines
Michel Habib, Algorithms for Some-join Decompositions of Graphs...... 15
Yaokun Wu, A -sweep LBFS Certifying Algorithm for Recognizing Interval Graphs
Min Xu, On the Restricted Forwarding Index Problem in Communication Networks
Jiming Guo, On the Laplacian Spectral Radius of Graphs
Changhong Lu, Identifying Codes and Locating-dominating Sets on Paths and Cycles
Lianzhu Zhang,Pfaffian Graphs Embedding on the Torus
Yijia Chen, The Parameterized Complexity of K-edge Induced Subgraphs
Yuqin Sun, A Bound for Size Ramsey Numbers of Multi-partite Graphs
Moo YoungSohn, Bondage Number of the Graph BundleHaving Reflection Voltage Assignment
Hye Kyung Kim, Note on Paired-domination Games...... 20
Han Ren, Finding More Short Cycles in (Embedded) Graphs...... 21
Huiqing Liu, Fault-tolerant Maximal Local-connectivity on Bubblesort Star Graphs
Yanmei Hong,Non-separating Cycles Avoiding Specific Vertices
Xiumei Wang, Characterizations of PM-compact Bipartite and Near-bipartite Graphs
1
Plenary Talks
Cops and Robber on a Random Graph
Nick Wormald
University of Waterloo
Coauthor: Pawel Pralat
Abstract:In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graphis called the cop number ofThe biggest open conjecture in this area is Meyniel's, which asserts that for some absolute constantthe cop number of every graphis at mostwhereWe show that Meyniel's conjecture holds asymptotically almost surely fora random-regular graph,as well as in the standard random graph model Joint work with Pawel Pralat.
Routing Cost Constrained Connected Dominating Sets
Ding-Zhu Du
University of Texas at Dallas
Abstract: In wireless networks, the connected dominating set (virtual backbone) plays an important role in topological control. Using the connected dominating set can reduce routing table size and communication cost. However, the length of routing path may increase, which may cause time delay; also, the road load balancing may get worse. To improve the performance of the connected dominating set, One has studied the routing cost constrained connected dominating set. In this talk, we present some new developments along this research direction.
Some Problems on Circular Colouringof Graphs
Xuding Zhu
Zhejiang Normal University
Abstract: Given a real numberand a grapha circular-colouring ofcolours vertices ofwith points in a circle of circumferenceso that colours assigned to adjacent vertices are at least distanceapart. The circular chromatic numberofis the infimum of thosefor whichhas a circular-colouring. The circular chromatic number of a graph is a refinement of its chromatic number. It contains more information about the structure of the graph. The concept of circular colouring of graphs has attracted considerable attention in the past twenty years, and has become an important branch of chromatic graph theory. There are many exciting results and new techniques, as well as many challenging open problems. This talk presents some open problems in this area.
Asymptotic Properties of Locally Restricted Compositions
Zhicheng Gao
University of Macao CarletonUniversity
Abstract: Roughly speaking, a locally restricted composition is a composition of an integer in which parts within a given distance of each other are required to satisfy some conditions. Carlitz compositions, in which adjacent parts must be distinct, are a classic example of such compositions. Compositions with local restrictions are usually much more complicated than unrestricted compositions from enumerative viewpoint. We survey some recent results about the asymptotic behavior of locally restricted compositions including number, joint normality of many parameters, largest part, and probability of gap-free. We use combinatorial arguments, generating functions and infinite transfer matrices.
Tutte Type Polynomials from Viewpoint of Homology and Cohomology
Beifang Chen
HongKongUniversity of Science and Technology
Abstract: The Tutte polynomial is a common generalization of the chromatic polynomial and the flow polynomial. It is well-known that the value of the flow polynomial at a positive integeris the number of nowhere-zero flows over an abelian group ofelements. This can be considered as counting the number of homology cycles which are nowhere-zero in the homology group. The chromatic polynomial is analogous when it is reduced to the tension polynomial which comes from the counting of nowhere-zero tensions in the cohomology group. I shall combine counting inside the homology and cohomology together to redefine the Tutte polynomial which automatically gives rise to a combinatorial/geometric interpretations for the Tutte polynomial and its likes. The homology group in the talk is termed as flow group while the cohomology group is termed as tension group.
Symmetric Graphs and Transitive Block Designs
Sanming Zhou
University of Melbourne
Abstract: Exploring symmetry of geometric objects has always been a fascinating topic in mathematics. In particular, in graph theory, since Tutte's seminal work (1947) on cubic symmetric graphs, there have been extensive researches on symmetries of graphs, which are usually measured in terms of their automorphism groups. In the case when the automorphism group of a graph contains a subgroup which is transitive on the set of arcs, the graph is said to be symmetric, where an arc is an ordered pair of adjacent vertices. Often the subgroup involved is imprimitive on the vertex set of the graph,that is, it leaves at least one nontrivial partition invariant. In this talk I will discuss recent progress on the study of imprimitive symmetric graphs with an emphasis on their connections with transitive block designs.
Keywords: Symmetric graph, arc-transitive graph, block design.
Invited Talks
Improving Performances of Selfish RingRouting via Limited Cooperations
Xiaodong Hu
Academy of Mathematics and Systems Science, ChineseAcademy of Sciences
Abstract: Selfish routing models network routing from a game-theoretic perspective, in which network users are viewed as self-interested strategic players participating in a competitive game. Each player, with his own pair of source and destination in the network, aims to establish a communication path (between his source and destination) along which he would experience latency or load as low as possible, given the link congestion caused by all other players. Despite the system objective to minimize the maximum latency among all source-destination pairs, network designers are often interested in a Nash equilibrium (NE) that is as close to the system optimum as possible, where the NE is a “stable state” among the players, from which no player has the incentive to deviate unilaterally. The (in)efficiency of NE is predominantly quantified by the so called price of anarchy (PoA), which is the worst-case ratio between the maximum latencies/load in a NE and in a system optimum. In this talk we will show that PoAs could be reduced via cooperation among only a small number of players, whereplayers cooperate only if none of them would experience a higher latency/load and at least one would experience a lower latency/load when simultaneous changing their routes.
Approximation Algorithms for a Bi-level Knapsack Problem
Guochuan Zhang
ZhejiangUniversity
Abstract: We consider a variant of the knapsack problem. There are two knapsacks with probably different capacities, owned by two agents, respectively. Given a set of items, each with a fixed size and a profit, the two agents select items and pack them into their own knapsacks under the capacity constraint. Same items can be packed simultaneously into different knapsacks. However, in this case the profit of such items may vary. One agent aims to maximize the total profit of items packed into her knapsack, while another agent can only pack items into her knapsack as well but she cares about the total profit of both knapsacks. The latter agent is a leader while the former is a follower. We are interested in designing approximation algorithms for the leader assuming that the follower is selfish. For different settings we provide approximation results.
Remarks for the Local Lemma
Yusheng Li
Department of Mathematics, TongjiUniversity
Abstract: Following an idea of Erdos and Spencer, it is shown that the dependency graph in the local lemma can be replaced by a sparser graph, which is a bipartite graph for most applications. This form can be used to improve the known results or simplify the previous proofs.
A Revised Proof of the Optimality for the Kise–Ibaraki–Mine Algorithm
Guochun Tang
ShanghaiSecondPolytechnicUniversity
Abstract: For the problem of scheduling -jobs on one-machine with agreeable job release dates and due dates to minimize the number of late jobs, Kise, Ibaraki and Mine [Operations Research, 26(1978)121–126] gave an-time algorithm and proved its optimality by four lemmas. Li et al. [Operations Research, 58(2010) 508–509] gave a counterexample to show that one lemma is invalid in some case and therefore the optimality is also invalid. In this paper, we revise the lemma and prove that the algorithm is still valid.
Total Coloring of Planar Graphs without Intersecting Short Cycles
Jianliang Wu
ShandongUniversity
Abstract: Letbe a planar graph withand for each vertexthere is an integersuch thathas at most one-cycle incident with Then the total chromatic number ofis
Scheduling with Machine Maintenance for Minsum Criteria
Zhiyi Tan
ZhejiangUniversity
Abstract: In the talk, we study scheduling problems with machine maintenance on single or parallel machines. There are machine nonavailability periods/operator nonavailability periods on some of the machines. If a job cannot be finished before a nonavailability period, it has to restart rather than continue. No job can be started or finished during the operator nonavailability period. The objective is to minimize the total completion time. Worst-case ratios of SPT and nonapproximability results are obtained for different situations.
The Surviving Rate of a Planar Graph
Weifan Wang
Zhejiang Normal University
Abstract: In this talk, we give a brief survey on the surviving rate of a graph. In particular, we discuss the surviving rate of planar graphs with high girth.
Arithmetic Operations over Regular Languages
Hong Zhu
EastChinaNormalUniversity
Abstract: Regular language is a classic topic in theory of computation. We consider the closure of arithemetic operations over the binary numbers if the numbers come from strings in the regular sets.
An Extension of the Chvάtal-Erdös Theorem:Counting the Number of Maximum Independent Sets
Liming Xiong
Department of Mathematics,Beijing Institute of Technology
Abstract:In 1972, Chvάtal and Erdös proved a well-known result that the graph with connectivitynot less than its independence numberis hamiltonian. We will strengthen the Chvάtal-Erdös theorem to the following: Letbe a simple -connected graph of ordersuch thatand such that the number of maximum independent sets of cardinalityis atmost Theniseither Hamiltonian ora subgraph of In this talk, we also present some other extensions of the Chvάtal-Erdös theorem.