Monotonicity in graph searching

D. Bienstock; Paul Seymour

doi:10.1016/0196-6774(91)90003-H

Monotonicity in graph searching

D. Bienstock
, Paul Seymour

Research output: Contribution to journal › Article › peer-review

211 Scopus citations

Abstract

We give a new proof of the result, due to A. LaPaugh, that a graph may be optimally "searched" without clearing any edge twice.

Original language	English (US)
Pages (from-to)	239-245
Number of pages	7
Journal	Journal of Algorithms
Volume	12
Issue number	2
DOIs	https://doi.org/10.1016/0196-6774(91)90003-H
State	Published - Jun 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/0196-6774(91)90003-H

Cite this

@article{566327b390914465b13e7537669e0e5e,

title = "Monotonicity in graph searching",

abstract = "We give a new proof of the result, due to A. LaPaugh, that a graph may be optimally {"}searched{"} without clearing any edge twice.",

author = "D. Bienstock and Paul Seymour",

year = "1991",

month = jun,

doi = "10.1016/0196-6774(91)90003-H",

language = "English (US)",

volume = "12",

pages = "239--245",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - Monotonicity in graph searching

AU - Bienstock, D.

AU - Seymour, Paul

PY - 1991/6

Y1 - 1991/6

N2 - We give a new proof of the result, due to A. LaPaugh, that a graph may be optimally "searched" without clearing any edge twice.

AB - We give a new proof of the result, due to A. LaPaugh, that a graph may be optimally "searched" without clearing any edge twice.

UR - https://www.scopus.com/pages/publications/0000839857

UR - https://www.scopus.com/pages/publications/0000839857#tab=citedBy

U2 - 10.1016/0196-6774(91)90003-H

DO - 10.1016/0196-6774(91)90003-H

M3 - Article

AN - SCOPUS:0000839857

SN - 0196-6774

VL - 12

SP - 239

EP - 245

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -

Monotonicity in graph searching

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this