
Published online:
01 September 2009
Published in print:
22 January 2009
Online ISBN:
9780191718755
Print ISBN:
9780198570837
Contents
-
-
-
-
-
-
-
3.1 A first example: The minimum spanning tree 3.1 A first example: The minimum spanning tree
-
3.1.1 Definition and basics of graph theory 3.1.1 Definition and basics of graph theory
-
3.1.2 An efficient algorithm 3.1.2 An efficient algorithm
-
-
3.2 General definitions 3.2 General definitions
-
3.3 More examples 3.3 More examples
-
3.3.1 Eulerian circuit 3.3.1 Eulerian circuit
-
3.3.2 Hamiltonian cycle 3.3.2 Hamiltonian cycle
-
3.3.3 Travelling salesman problem 3.3.3 Travelling salesman problem
-
3.3.4 Assignment 3.3.4 Assignment
-
3.3.5 Satisfiability 3.3.5 Satisfiability
-
3.3.6 Colouring and vertex covering 3.3.6 Colouring and vertex covering
-
3.3.7 Number partitioning 3.3.7 Number partitioning
-
-
3.4 Elements of the theory of computational complexity 3.4 Elements of the theory of computational complexity
-
3.4.1 The worst-case scenario 3.4.1 The worst-case scenario
-
3.4.2 Polynomial or not? 3.4.2 Polynomial or not?
-
3.4.3 Optimization, evaluation, and decision 3.4.3 Optimization, evaluation, and decision
-
3.4.4 Polynomial reduction 3.4.4 Polynomial reduction
-
3.4.5 Complexity classes 3.4.5 Complexity classes
-
3.4.6 P = NP? 3.4.6 P = NP?
-
3.4.7 Other complexity classes 3.4.7 Other complexity classes
-
-
3.5 Optimization and statistical physics 3.5 Optimization and statistical physics
-
3.5.1 General relation 3.5.1 General relation
-
3.5.2 Spin glasses and maximum cuts 3.5.2 Spin glasses and maximum cuts
-
-
3.6 Optimization and coding 3.6 Optimization and coding
-
Notes Notes
-
-
-
-
-
-
-
-
-
-
-
-
-
Chapter
3 Introduction to combinatorial optimization
Get access
Pages
47–64
-
Published:January 2009
Cite
Mézard, Marc, and Andrea Montanari, 'Introduction to combinatorial optimization', Information, Physics, and Computation, Oxford Graduate Texts (Oxford , 2009; online edn, Oxford Academic, 1 Sept. 2009), https://doi.org/10.1093/acprof:oso/9780198570837.003.0003, accessed 29 Apr. 2025.
Abstract
This chapter provides an elementary introduction to some basic concepts in theoretical computer science. It includes basic notions of graph theory and an informal introduction to computational complexity, presenting the basic classes P, NP, and NP-complete. These notions are illustrated by discussions of the minimal spanning tree and satisfiability problems, and by applications from statistical physics (spin glasses and maximum cuts), and from coding theory (decoding complexity).
Keywords:
computational complexity, NP-complete, graph theory, satisfiability, spin glasses, decoding complexity, minimal spanning tree
Collection:
Oxford Scholarship Online
You do not currently have access to this chapter.
Sign in
Personal account
- Sign in with email/username & password
- Get email alerts
- Save searches
- Purchase content
- Activate your purchase/trial code
- Add your ORCID iD
Purchase
Our books are available by subscription or purchase to libraries and institutions.
Purchasing informationMetrics
View Metrics
Metrics
Total Views
215
141
Pageviews
74
PDF Downloads
Since 10/1/2022
Month: | Total Views: |
---|---|
October 2022 | 22 |
November 2022 | 10 |
December 2022 | 5 |
January 2023 | 5 |
March 2023 | 3 |
April 2023 | 9 |
May 2023 | 9 |
September 2023 | 7 |
October 2023 | 7 |
November 2023 | 5 |
December 2023 | 7 |
January 2024 | 10 |
February 2024 | 1 |
March 2024 | 9 |
April 2024 | 14 |
May 2024 | 10 |
June 2024 | 7 |
July 2024 | 11 |
August 2024 | 7 |
September 2024 | 15 |
October 2024 | 3 |
November 2024 | 7 |
December 2024 | 5 |
January 2025 | 6 |
February 2025 | 5 |
March 2025 | 5 |
April 2025 | 11 |
Citations
Altmetrics
More from Oxford Academic
Get help with access
Institutional access
Access to content on Oxford Academic is often provided through institutional subscriptions and purchases. If you are a member of an institution with an active account, you may be able to access content in one of the following ways:
IP based access
Typically, access is provided across an institutional network to a range of IP addresses. This authentication occurs automatically, and it is not possible to sign out of an IP authenticated account.
Sign in through your institution
Choose this option to get remote access when outside your institution. Shibboleth/Open Athens technology is used to provide single sign-on between your institution’s website and Oxford Academic.
If your institution is not listed or you cannot sign in to your institution’s website, please contact your librarian or administrator.
Sign in with a library card
Enter your library card number to sign in. If you cannot sign in, please contact your librarian.
Society Members
Society member access to a journal is achieved in one of the following ways:
Sign in through society site
Many societies offer single sign-on between the society website and Oxford Academic. If you see ‘Sign in through society site’ in the sign in pane within a journal:
If you do not have a society account or have forgotten your username or password, please contact your society.
Sign in using a personal account
Some societies use Oxford Academic personal accounts to provide access to their members. See below.
Personal account
A personal account can be used to get email alerts, save searches, purchase content, and activate subscriptions.
Some societies use Oxford Academic personal accounts to provide access to their members.
Viewing your signed in accounts
Click the account icon in the top right to:
Signed in but can't access content
Oxford Academic is home to a wide variety of products. The institutional subscription may not cover the content that you are trying to access. If you believe you should have access to that content, please contact your librarian.
Institutional account management
For librarians and administrators, your personal account also provides access to institutional account management. Here you will find options to view and activate subscriptions, manage institutional settings and access options, access usage statistics, and more.