✦ LIBER ✦

Marshals, monotone marshals, and hypertree-width

✍ Scribed by Isolde Adler

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 193 KB
Volume: 47
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20025

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The tree‐width of a hypergraph H equals one less than the number of cops necessary to catch the robber in the Monotone Robber and Cops Game played on H. Analogously, the hypertree‐width of a hypergraph is characterised by the Monotone Robber and Marshals Game. While the Robber and Cops Game and its monotone variant coincide, Gottlob, Leone and Scarcello stated the corresponding question for the Robber and Marshals Game as an open problem. We give a negative answer. Concerning the generalised hypertree‐width, our counterexamples show that it is neither characterised by the Robber and Marshals Game nor by its monotone variant. We conclude by resuming how these hypergraph invariants are related. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 275–296 2004

📜 SIMILAR VOLUMES

Robbers, marshals, and guards: game theo

Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width

✍ Georg Gottlob; Nicola Leone; Francesco Scarcello 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 501 KB

In a previous paper (J. Comput. System Sci. 64 (2002) 519), the authors introduced the notion of hypertree decomposition and the corresponding concept of hypertree width and showed that the conjunctive queries whose hypergraphs have bounded hypertree width can be evaluated in polynomial time. Bounde

The Marshal and the murderer: a Marshal Guarnaccia investigation

✍ Magdalen Nabb 📂 Fiction 📅 2015;2002 🏛 Soho Press 🌐 en-US ⚖ 144 KB 👁 2 views

A young Swiss art student who commutes to a small town near Florence is reported missing. Then her body is found. Was it a sex crime? Guarnaccia suspects a local feud with its roots in World War II.

Police stress, state-trait anxiety, and

Police stress, state-trait anxiety, and stressors among U.S. Marshals

✍ Deborah Wilkins Newman; M. LeeAnne Rucker-Reed 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 136 KB

Unlike previous studies on stress in local police officers, this study was unique in that it used Deputy U.S. Marshals as the population pool. This study replicated the study conducted by Storch and Panzarella (1996) who determined stress levels and stressors of police officers. A standardized inven

The Marshal and the Madwoman

✍ Nabb, Magdalen 📂 Fiction 📅 2009;2003 🏛 Soho Press 🌐 English ⚖ 150 KB 👁 2 views

Out giving his wife driving lessons, Marshal Guarnaccia of the Carabinieri witnesses a disturbance in the streets involving a local eccentric, "crazy Clementina." When the woman is found dead in her apartment soon after the incident, of an apparent suicide, the marshal is puzzled and immediately sus

Testing for exponential and marshall–olk

Testing for exponential and marshall–olkin distributions

✍ Sándor Csörgo&#x030B;; A.H. Welsh 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 812 KB

The Marshal and the Bride on the Run

✍ Wake, Indiana 📂 Fiction 📅 2019 🏛 Fair Havens Books 🌐 English ⚖ 94 KB 👁 3 views