Combinatorial Optimization and Graph Algorithms Communications of NI
Covering network designs, discrete convex analysis, facility location and clustering problems, matching games, and parameterized complexity, this book discusses theoretical aspects of combinatorial optimization and graph algorithms. Contributions are by r
- PDF / 2,439,510 Bytes
- 126 Pages / 453.543 x 683.15 pts Page_size
- 37 Downloads / 243 Views
Combinatorial Optimization and Graph Algorithms Communications of NII Shonan Meetings
Combinatorial Optimization and Graph Algorithms
Takuro Fukunaga Ken-ichi Kawarabayashi •
Editors
Combinatorial Optimization and Graph Algorithms Communications of NII Shonan Meetings
123
Editors Takuro Fukunaga National Institute of Informatics Tokyo Japan
ISBN 978-981-10-6146-2 DOI 10.1007/978-981-10-6147-9
Ken-ichi Kawarabayashi National Institute of Informatics Tokyo Japan
ISBN 978-981-10-6147-9
(eBook)
Library of Congress Control Number: 2017948610 © Springer Nature Singapore Pte Ltd. 2017 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Printed on acid-free paper This Springer imprint is published by Springer Nature The registered company is Springer Nature Singapore Pte Ltd. The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore
Preface
In a very short time since the concept of “P” and “NP” was introduced, algorithmic aspect of mathematics and computer science has quickly gained explosion of interest from the research community. Indeed, the problem of whether P = NP (or P 6¼ NP) is one of the most outstanding open problems in all of mathematics. A wider class of problems from mathematics, computer science, and perhaps operations research has been known to be NP-complete, and even today, the collection of NP-complete problems grows almost every few hours. In order to understand NP-hard problems, the research community comes to have a fairly good understanding of combinatorial structures in the past 40 years. In particular, the algorithmic aspects of fundamental problems in graph theory (i.e., graph algorithm) and in optimization (i.e., combinatorial optimization) are two of the main areas that the research community have some deep understandings. Graph algorithm is an area in computer science that tries to desig
Data Loading...