Graph Theory, Combinatorics, and Algorithms_ Interdisciplinary Applications [Golumbic & Hartman 2005-08-26].pdf

(1727 KB) Pobierz
GRAPH THEORY,
COMBINATORICS AND
ALGORITHMS
INTERDISCIPLINARY
APPLICATIONS
GRAPH THEORY,
COMBINATORICS AND
ALGORITHMS
INTERDISCIPLINARY
APPLICATIONS
Edited by
Martin Charles Golumbic
Irith Ben-Arroyo Hartman
Martin Charles Golumbic
University of Haifa, Israel
Irith Ben-Arroyo Hartman
University of Haifa, Israel
Library of Congress Cataloging-in-Publication Data
Graph theory, combinatorics, and algorithms / [edited] by Martin Charles Golumbic,
Irith Ben-Arroyo Hartman.
p. cm.
Includes bibliographical references.
ISBN-10: 0-387-24347-X
ISBN-13: 978-0387-24347-4
e-ISBN 0-387-25036-0
1. Graph theory. 2. Combinatorial analysis. 3. Graph theory—Data processing.
I. Golumbic, Martin Charles. II. Hartman, Irith Ben-Arroyo.
QA166.G7167 2005
511 .5—dc22
2005042555
Copyright
C
2005 by Springer Science + Business Media, Inc.
All rights reserved. This work may not be translated or copied in whole or in part without the written
permission of the publisher (Springer Science + Business Media, Inc., 233 Spring Street, New York, NY
10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection
with any form of information storage and retrieval, electronic adaptation, computer software, or by similar
or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks and similar terms, even if they are
not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to
proprietary rights.
Printed in the United States of America.
9 8 7 6 5 4 3 2 1
springeronline.com
SPIN 11374107
Contents
Foreword
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chapter 1
Optimization Problems Related to Internet Congestion
Control
Richard Karp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
1
17
41
Chapter 2
Problems in Data Structures and Algorithms
Robert Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chapter 3
Algorithmic Graph Theory and its Applications
Martin Charles Golumbic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chapter 4
Decompositions and Forcing Relations in Graphs and Other
Combinatorial Structures
Ross McConnell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chapter 5
The
Local Ratio
Technique and its Application to Scheduling
and Resource Allocation Problems
Reuven Bar-Yehuda, Keren Bendel, Ari Freund and Dror Rawitz
Domination Analysis of Combinatorial Optimization
Algorithms and Problems
Gregory Gutin and Anders Yeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
107
Chapter 6
145
Chapter 7
On Multi-Object Auctions and Matching Theory:
Algorithmic Aspects
Michal Penn and Moshe Tennenholtz . . . . . . . . . . . . . . . . . . . . . . . .
Chapter 8
Strategies for Searching Graphs
Shmuel Gal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
173
189
215
Chapter 9
Recent Trends in Arc Routing
Alain Hertz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chapter 10
Software and Hardware Testing Using Combinatorial
Covering Suites
Alan Hartman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Incidences
Janos Pach and Micha Sharir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
237
267
Chapter 11

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin