肖鳴宇
肖鳴宇
肖鳴宇 電子科技大學計算機科學與工程學院教授、博士生導師，協同自主計算實驗室。多個基本NP難問題的最佳參數和精確演演算法的保持者，在圖的多分割問題上解決了多個公開難題，在參數演演算法上是國內最為活躍的科研工作者之一。
"在香港中文大學師從圖靈獎獲得者姚期智先生，從事理論計算機方向博士學習三年獲得博士學位。清華大學、京都大學、巴黎第九大學等高校訪問學者。科研方向包括：演演算法與計算複雜度分析，圖論及圖演演算法，智能演演算法，最優化，參數演演算法等。
和日本、加拿大、美國、法國、以色列、香港等地許多計算機專家建立了學術合作關係。目前是多個基本NP難問題的最佳參數和精確演演算法的保持者，在精確演演算法和參數演演算法上是國內最為活躍的科研工作者之一。主持國家自然科學基金4項。近五年第一作者發表高水平學術論文50餘篇。
| 姓名：肖鳴宇 | 性別：男 | 學校：電子科技大學 |
| 系別：軟體系 | 職稱：教授、博士生導師 | 畢業院校：中南大學 |
| 學歷：博士 | 實驗室：協同自主計算實驗室 | 電話： |
| 研究方向：演演算法設計與分析，計算複雜度分析，近似演演算法，參數演演算法，圖論及圖演演算法，計算機輔助幾何設計等 | ||
2008年，博士，計算機，香港中文大學（The Chinese University of Hong Kong）
2009年6月，2010年7月，訪問學者，京都大學（Kyoto University）
2011年9-11月，訪問學者，巴黎九大（University Paris Dauphine）
肖鳴宇在香港中文大學師從圖靈獎獲得者姚期智 先生，從事理論計算機方向學習三年獲得博士學位。和日本、加拿大、美國、法國、以色列、香港等地許多計算機專家建立了學術合作關係。目前是多個基本NP難問題的最佳參數和精確演演算法的保持者，在圖多分割問題上解決了多個公開難題，在參數演演算法上是國內最為活躍的科研工作者之一。主持國家自然科學基金4項。近四年第一作者發表高水平學術論文近40篇，其中8篇屬於CCF認定的B類及以上刊物，7篇屬於CCF認定C類刊物。
目前主要從事參數演演算法和精確演演算法方向研究。在《Algorithmica》等國際頂級演演算法雜誌和會議上第一作者發表論文20餘篇（具體列表參看DBLP或谷歌主頁）。主持國家自然科學基金青年項目《圖上若干基本NP難問題的演演算法研究》、國際交流與合作項目《獨立集、點覆蓋及其相關問題的參數演演算法和精確演演算法研究》等三項國家級項目。
肖鳴宇老師一直從事演演算法方向研究工作，他的研究成果之一：為獨立集問題設計了當前最快的精確演演算法，是近30年來第一次真正打破Robson於1986年給出的運行時間上界，並在亞太地區演演算法與計算領域最好的會議ISAAC 2013上獲最佳論文提名；2013年獲國家自然科學基金面上資助，發表第一作者論文10篇（其中SCI 5篇，CCF B類4篇），獲校學術新人獎，是計算機學科第一位獲得該資助的青年老師。肖鳴宇老師承擔的課程被評定優秀，同時他還擔任了數理基科班和學院珠峰計劃導師，指導本科生髮表一級學報論文1篇。
1.基於“測量治之”方法的演演算法設計研究，國家自然科學基金，主持
2. 圖上若干基本NP難問題的演演算法研究，國家自然科學基金，主持
3. 獨立集、點覆蓋及其相關問題的精確演演算法和參數演演算法研究，國家自然科學基金，主持
4. Online Optimization for Dynamic Power Management, 國家自然科學基金，中方主持
5. 參數演演算法理論及其應用研究，中央高校基金，主持
6. 圖分割問題的參數演演算法研究，電子科技大學校青年科學基金，主持
| 博士招生專業 | 碩士招生專業 |
| 081202計算機軟體與理論 | 081202計算機軟體與理論 |
04方向：計算生物學 06方向：計算智能 08方向：複雜網路分析 | 02方向：資料庫與數據挖掘 05方向：計算理論與技術 10方向：計算生物學 |
肖鳴宇
這是理論計算領域應用十分廣泛且最為基礎的難計算問題之一。近30年來，圍繞這個獨立集問題精確演演算法的研究論文不下20篇，但都沒有超越羅賓遜的研究——肖鳴宇卻使“羅賓遜”又往前走了一大步。
2013年底，當肖鳴宇應邀參加在香港舉行的第25屆國際演演算法與計算大會（ISAAC）時，此文作為重要研究成果，入選大會“最佳論文”候選論文，並受到業內學者的高度關注。
肖鳴宇沒有拿過多少“大項目”，而是一門心思深入到“收效周期很長”的基礎計算理論研究，並樂此不疲。雖然這項研究的更大價值或許要在5年之後才能充分顯現，但他認為，作為基礎與前沿理論的研究者，這已足以讓他感到快慰了。
肖鳴宇本科時就讀於中南大學數學系，做的最多且最有樂趣的事情，就是參加數學建模競賽。當時，他在同學們眼裡是當之無愧的數學建模高手，曾在美國數學建模競賽中連續兩次斬獲一等獎。
從數學到計算機，只有一步之遙，數學建模或演演算法研究就是這樣一種數學與計算機交叉融合的典型。很多學科都會遇到數學建模或演演算法研究，肖鳴宇的所有努力可以劃分為兩個步驟：第一是對問題進行優化建模，第二是對優化模型進行演演算法設計來求解。
他對演演算法很感興趣，但一直沒有系統學習過，而是隨著“求解”的需要，東一榔頭、西一棒槌，現學現用。2002年和2005年他在中南大學分別獲得數學學士和碩士學位，並獲得湖南省優秀畢業論文和湖南省優秀畢業生稱號——但這些與演演算法沒有多少關聯，直到上博士當助教時，為了給香港中文大學的本科生講課，他才系統接觸了演演算法課程。
以此為標誌，他徹底從數學轉入演演算法研究，再也沒有變更過方向。演演算法是計算機領域內十分基礎的理論，他說，“計算機是死的，你得用演演算法告訴它做什麼、怎麼做，因此，計算機的智慧就取決於你的思想！”
其實，肖鳴宇並非從一開始就選擇演演算法為畢生事業，當他在數學的海洋遨遊時，甚至從未想到自己以後會和演演算法結下如此深厚的情誼。促使他發生轉變的是一個“中南傳奇”：二十年前，有一位數學天才轉行做了演演算法研究，並成為演演算法領域的巨擘。
這個人就是美籍華人學者、當時中南大學的“長江學者”陳建二教授。陳建二多年來主要從事計算機理論及應用技術的研究，在計算複雜性理論、圖理論與演演算法、計算優化理論、網路理論等領域內進行了深入系統的研究，取得了一批具有世界領先水平的理論成果。
一位數學奇才何以轉入演演算法領域？帶著這個困惑和對自己未來方向的思索，肖鳴宇鼓起勇氣求教陳建二教授。他聽完肖鳴宇的疑問之後，並沒有直接回答，而是隨口出了幾個演演算法難題；肖鳴宇略加思索，即給出了自己的答案。這讓陳建二頓時對眼前的這個小夥子刮目相看，他認為，肖鳴宇的解決思路與演演算法領域近十年來的前沿思想十分吻合，甚至有一些思路獨闢蹊徑，有過之而無不及。
於是，陳建二果斷建議肖鳴宇向演演算法研究轉型，“雖然做數學研究也可以做出傑出的成就，但如果不做演演算法研究就太可惜了！”在肖鳴宇碩士畢業時，陳建二欣然為他寫了推薦信，薦他到香港中文大學蔡雷震教授麾下學習。不料，蔡雷震憐愛肖鳴宇之才，立即鼎力推薦給了學界泰斗——姚期智院士。
姚期智是世界著名計算機學家、美國科學院院士、美國科學與藝術學院院士、中國科學院外籍院士，2000年“圖靈獎”得主。2004年9月，他辭去美國普林斯頓大學的終身教職，正式加盟清華大學高等研究中心，成為清華的全職教授，並於2005年成為香港中文大學的博文講座教授。
2005年，肖鳴宇在蔡雷震的推薦下，在香港中文大學見到了他的博士生導師姚期智。3年後，他就獲得了哲學博士學位，成為姚期智在香港中文大學培養出的第一位博士，也是2008年香港中文大學計算機系僅有的兩位三年畢業的博士之一。
第一次與導師見面時，肖鳴宇並沒有立即引起姚期智的特別注意。與如此大師級的學者面對面交談，讓他感覺很緊張。見面之前他已做了充分準備，“以為會問到很高層次的問題，所以準備時和見面回答時，都努力往哲學方面靠，結果適得其反，給姚老師留下了一種誇誇其談的形象！”姚期智的考察很實在、很直接，只說了一句“你把Ramsey定理給我證明一遍”。這次見面，讓肖鳴宇學到了很多，也對導師的求實和嚴謹精神由衷地敬佩。
半年後，姚期智給了第二次見面的機會。經過半年的調整和摸索，肖鳴宇把自己半年來的思考和想法實實在在地做了彙報，讓姚期智十分滿意，他認為肖鳴宇的進步超乎想象。肖鳴宇也從此獲得了更多的見面機會，並有機會聆聽更多的指導。
經過幾次見面交流，姚期智對肖鳴宇在演演算法方面的靈感和問題意識非常看好。在第三次見面時，他對肖鳴宇的研究方向進行了充分的評估，建議他在“圖演演算法”和“NP難問題”領域開疆擴土。當時，姚期智主攻“量子計算”，肖鳴宇也曾考慮這個方向，但姚期智卻認為肖鳴宇在“圖演演算法”和“NP難問題”方面將會取得更大的成就。
此後，肖鳴宇不負所望，在演演算法領域非常前沿的“圖多優化分割問題”研究中取得巨大進展。當時“圖多優化分割問題”研究中有多個懸而未決的“公認難題”，肖鳴宇沉浸其中，高度專註，在一周內破解了其中一個難題。當他把最終研究結果報告給“副導師”蔡雷震后，蔡雷震十分重視，但沒有立即給出答覆，而是報告給姚期智。
事後才知道，兩位導師都在獨立地對該研究進行科學嚴謹的驗證。一個月後，肖鳴宇再次見到姚期智，驚訝地發現辦公桌上有100多頁的手寫演算稿紙，對自己研究中的每個步驟都給予了推導和證明——結論是正確的！
以此為開端，肖鳴宇在博士期間獲得了大豐收，不僅成為國內演演算法理論方向最為活躍的科研者之一，也是多個基本NP難問題最佳參數演演算法和精確演演算法的保持者。姚期智、王魯生等教授曾這樣評價肖鳴宇：“他研究的這些問題都十分重要，其中大部分問題被國際頂尖學者廣泛研究。我們相信，他將在這些領域取得更顯著的進展！”
在參數演演算法基本問題的“Benchmark列表”中，收錄著肖鳴宇的兩項研究結果，是僅有的兩項來自中國的研究結果。他提出的複雜參數方法簡化並改進了很多基本參數演演算法，被國際同行評價為“有趣並有前景”。
一個又一個公認難題的解決，讓肖鳴宇在學術界聲名鵲起，姚期智也大力推薦這位得意弟子參加相關的國內外高級別學術會議，讓肖鳴宇大開了眼界，同時也在國際學術界獲得了聲譽。
博士畢業后，日本京都大學每年都邀請肖鳴宇赴日本訪問交流，並且每年都派人來中國學習。肖鳴宇加盟電子科大后，京都大學的學者每年都來清水河畔拜訪他。京都大學為肖鳴宇專門留出寬敞的辦公室，並邀請他“任何時候都可以來京都大學辦公”。
“成名”之後，肖鳴宇本來有更多的機會獲取更多的資源做“應用研究”，但是，他一直不肯邁出這一步。導師姚期智也十分希望肖鳴宇堅持做“理論研究”而非“應用研究”，他曾對肖鳴宇說：“我相信你有能力在應用研究中解決一些重大問題，但如果在基礎理論研究中取得突破，將會對學術界和產業界產生更大、更為深遠的影響。”
因此，從博士畢業到現在，肖鳴宇都把自己定位在基礎計算理論研究。“解決大家都解決不了的難題或不願意投身研究的基礎問題，也是一種成功的學術路徑”，他說，“我就是那種專註地解決難題的人！”
肖鳴宇說到做到，從2008年加盟電子科大，他一直致力於基礎研究，沒有接過任何“橫向項目”。“圖多優化分割”理論在計算機、集成電路的生產中具有十分廣泛而重要的應用價值，華為等公司多次邀請肖鳴宇做“橫向項目”，助力解決相關技術難題，但肖鳴宇都決然地拒絕了。2009年，他只做成了一件事情，就是成功申請了一項國家自然科學基金——《圖上若干基本NP難問題的演演算法研究》。
“從理論研究到產業應用有一定的距離，我的精力有限，沒有更多的時間去解決應用領域的問題，所以只能集中力量深入研究基礎理論！”肖鳴宇說，“我相信，只要基礎理論獲得突破，從理論到應用的實現環節肯定會有其他優秀的人才努力完成！”
然而，純粹沉浸在基礎理論研究，對心態和定力是一種極大的考驗。經濟收入、量化考評、職稱晉陞等，既是對基礎理論研究者的壓力，也是對他們的極大誘惑。但是，肖鳴宇對此淡然處之，一直選擇在基礎理論領域堅守！
由於“圖演演算法”和“NP難問題”等領域曲高和寡，國際上相關的學術期刊影響因子較小，論文引用數量不大。而國內的相關研究因起步較晚，氣氛並未廣泛形成，目前大陸僅有清華、北大、上海交大、中南大學等少數幾所高校致力於此。但是，肖鳴宇並不在乎“熱門”還是“冷門”，而是持之以恆，並希望把我國西南地區的這個學科方向撐起來！
近幾年來，肖鳴宇每年都參加許多次各種計算理論方向的重要國際會議，從最開始的“默默無聞”逐步發展為今天的“備受矚目”，肖鳴宇也將“電子科大”推介到了重要的國際學術會議，使其成為國際國內同行最為熟知的內地高校之一。“做大做強計算機基礎與前沿理論，這是我的興趣，也是我的責任！”肖鳴宇說，“做基礎理論研究需要靜心靜氣，在這條路上，我將一如既往、風雨兼程！”
Mingyu Xiao:A New Linear Kernel for Undirected Planar Feedback Vertex Set: Smaller and Simpler.AAIM 2014: 288-298
Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Dominating Induced Matching Based on Graph Partition.CoRR abs/1408.6196(2014)
Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Annotated Edge Dominating Set in Graphs with Degree Bounded by 3.IEICE Transactions 96-D(3): 408-418 (2013)
Mingyu Xiao,Hiroshi Nagamochi:Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs.Theor. Comput. Sci. 469: 92-104 (2013)
Mingyu Xiao,Takuro Fukunaga,Hiroshi Nagamochi:FPTASs for trimming weighted trees.Theor. Comput. Sci. 469: 105-118 (2013)
Mingyu Xiao,Hiroshi Nagamochi:Parameterized edge dominating set in graphs with degree bounded by 3.Theor. Comput. Sci. 508: 2-15 (2013)
Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New parameterized algorithms for the edge dominating set problem.Theor. Comput. Sci. 511: 147-158 (2013)
Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs.FAW-AAIM 2013: 72-83
Mingyu Xiao,Hiroshi Nagamochi:An Improved Exact Algorithm for Undirected Feedback Vertex Set.COCOA 2013: 153-164
Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Maximum Independent Set.ISAAC 2013: 328-338
Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure.TAMC 2013: 96-107
Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Maximum Independent Set.CoRR abs/1312.6260(2013)
Mingyu Xiao,Hiroshi Nagamochi:An FPT algorithm for edge subset feedback edge set.Inf. Process. Lett. 112(1-2): 5-9 (2012)
Mingyu Xiao,Hiroshi Nagamochi:An Improved Exact Algorithm for TSP in Degree-4 Graphs.COCOON 2012: 74-85
Bruno Escoffier,Jérôme Monnot,Vangelis Th. Paschos,Mingyu Xiao:New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set.IPEC 2012: 25-36
Mingyu Xiao,Jiong Guo:A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments.MFCS 2012: 825-835
Mingyu Xiao,Hiroshi Nagamochi:A Refined Exact Algorithm for Edge Dominating Set.TAMC 2012: 360-372
Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure.CoRR abs/1212.6831(2012)
Mingyu Xiao,Leizhen Cai,Andrew Chi-Chih Yao:Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimumk-Way Cut Problem.Algorithmica 59(4): 510-520 (2011)
Mingyu Xiao,Hiroshi Nagamochi:Parameterized Edge Dominating Set in Cubic Graphs - (Extended Abstract).FAW-AAIM 2011: 100-112
Mingyu Xiao,Hiroshi Nagamochi:Further Improvement on Maximum Independent Set in Degree-4 Graphs.COCOA 2011: 163-178
Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New Parameterized Algorithms for the Edge Dominating Set Problem.MFCS 2011: 604-615
Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New parameterized algorithms for edge dominating set.CoRR abs/1104.4160(2011)
Mingyu Xiao:Finding minimum 3-way cuts in hypergraphs.Inf. Process. Lett. 110(14-15): 554-558 (2010)
Mingyu Xiao:Simple and Improved Parameterized Algorithms for Multiterminal Cuts.Theory Comput. Syst. 46(4): 723-736 (2010)
Mingyu Xiao:Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs.COCOA (2) 2010: 387-400
Mingyu Xiao:A Note on Vertex Cover in Graphs with Maximum Degree 3.COCOON 2010: 150-159
Mingyu Xiao,Takuro Fukunaga,Hiroshi Nagamochi:FPTAS's for Some Cut Problems in Weighted Trees.FAW 2010: 210-221
Mingyu Xiao:A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs.WALCOM 2010: 281-292
肖鳴宇教授除完成本科教學任務外，每年都會招收多名研究生。對於科研工作出色的學生，將推薦到海外交流或深造。其科研分為基礎科研和工程應用兩部分，具體參照如下：
1.基礎科研：建議想從事基礎演演算法研究的學生報考，特別是有一定數學分析能力或競賽經歷的同學。此方向的學習將大大加強學生的科研基礎。對於有志將來從事科研工作和出國深造的同學，可以考慮學習此方向。科研內容主要包括：演演算法分析與設計，優化演演算法，圖論及圖演演算法等。
該方向主要希望培養未來的大學教授和科研者，當然也包括大公司的高級研發人員。學生學習階段以學習和發表學術論文為主，論文達到一定級別則可推薦海外交流。
2. 工程應用：肖鳴宇教授也會招收工程方向的學生，該部分學生主要由實驗室聯合培養，從事雲計算方面的工程學習和鍛煉。學生將進入雲計算及相關實驗室學習研究，同時將可能獲得其他資深老師的指導。
