文档介绍：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 Irith Ben-Arroyo Hartman
University of Haifa, Israel 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.
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 SPIN 11374107
Contents
Foreword ............................................................. vii
Chapter 1 Optimization Problems Related to Congestion
Control
Richard Karp ............................................. 1
Chapter 2 Problems in Data Structures and Algorithms
Robert Tarjan .............................