圖論中的圖分割與圖匹配問題（英文版） [SOME ADVANCED TOPICS OF GRAPH PARTITIONING AND MATCHING PROBLEMS] pdf epub mobi txt 电子书 下载 2025

☆☆☆☆☆

張曉岩，張贊波 著

圖書標籤:

• 圖論
• 圖分割
• 圖匹配
• 組閤優化
• 算法
• 離散數學
• 計算機科學
• 網絡分析
• 優化問題
• 復雜網絡

出版社： 科学出版社

ISBN：9787030495020

版次：1

商品编码：12114972

包装：平装

外文名称：SOME ADVANCED TOPICS OF GRAPH PARTITIONING AND MATCHING PROBLEMS

开本：16开

出版时间：2017-01-01

用纸：胶版纸

页数：150

正文语种：英文

內容簡介

　　This work is our selected results of research on graph partitioning and matching problems in the field of theoretical computer science and structural graph theory in recent years. After an introductory chapter， the reader will find six chapters， each of which is written as a self-contained content. In the first part of the work， Chapter 2 through 4， we concentrate on the complexity， inapproximability， approximation algorithms and on-line algorithms of some graph vertex partitioning problems. In the second part of the work， Chapter 5 through 7， we focus on the structural properties of some graph problems related to matching wluch can be regarded as edge partitioning problems. We refer to the listed chapters for the details of the results.
　　Chapter 1 contains a short general introduction to the topics of the book and gives an overview of the main results， together with some motivation and connections to and relationships with older results. Specific terminology and notation can be found just before each of the topic8.
　　In Chapter 2， we first investigate the computational complexity of problems of determining the minimum number of monochromatic cliques or rainbow cycles that， respectively， partition the vertex set V(G) of a graph G. We show that the minimum monochromatic clique partition problem is APX-hard on K4 -free graphs and monochromatic-K4 -free graphs， and APX-complete on monochromatic-K4 - free graphs in which the size of a max：imum monochromatic clique is bounded by a constant. We also show that the minimum rainbow cycle partition problem is NP-complete， even if the input graph G is triangle-free. Moreover， for the weighted version of the minimum monochromatic clique partition problem on monochromatic-K4 -free graphs， we derive an approximation algorithm with (tight) approximation guarantee In |V (G)|+1.

內頁插圖

目錄

前言/序言

　　This work is our selected results of research on graph partitioning and matching problems in the field of theoretical computer science and structural graph theory in recent years. After an introductory chapter， the reader will find six chapters， each of which is written as a self-contained content. In the first part of the work， Chapter 2 through 4， we concentrate on the complexity， inapproximability， approximation algorithms and on-line algorithms of some graph vertex partitioning problems. In the second part of the work， Chapter 5 through 7， we focus on the structural properties of some graph problems related to matching wluch can be regarded as edge partitioning problems. We refer to the listed chapters for the details of the results.
　　Chapter 1 contains a short general introduction to the topics of the book and gives an overview of the main results， together with some motivation and connections to and relationships with older results. Specific terminology and notation can be found just before each of the topic8.
　　In Chapter 2， we first investigate the computational complexity of problems of determining the minimum number of monochromatic cliques or rainbow cycles that， respectively， partition the vertex set V(G) of a graph G. We show that the minimum monochromatic clique partition problem is APX-hard on K4 -free graphs and monochromatic-K4 -free graphs， and APX-complete on monochromatic-K4 - free graphs in which the size of a max：imum monochromatic clique is bounded by a constant. We also show that the minimum rainbow cycle partition problem is NP-complete， even if the input graph G is triangle-free. Moreover， for the weighted version of the minimum monochromatic clique partition problem on monochromatic-K4 -free graphs， we derive an approximation algorithm with (tight) approximation guarantee In |V (G)|+1.

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆