And/or-convexity: a graph convexity based on processes and deadlock models

DOI10.1007/S10479-017-2666-1MaRDI QIDQ1639288zbMATH OpenOpenAlexFDO

Authors Fábio Protti, Dieter Rautenbach, Uéverton S. Souza, Carlos Vinícius G. C. Lima, Jayme L. Szwarcfiter

Publication date 12 June 2018

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-017-2666-1

zbMATH Keywords

AND-OR modeland/or graphsdeadlockgraph convexity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deletion graph problems based on deadlock resolution
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Using Barrier Graphs for Deadlock Prevention in Communication Networks
• Deadlock Prevention in Process Control Computer Systems
• Revisiting deadlock prevention: a probabilistic approach

Cites work

• A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem
• A linear algorithm for the domination number of a tree
• A randomized competitive algorithm for evaluating priced AND/OR trees
• A two-level distributed detection algorithm of AND/OR deadlocks
• Characterization and recognition of Radon-independent sets in split graphs
• Completeness in approximation classes beyond APX
• Complexity aspects of the computation of the rank of a graph
• Complexity results related to monophonic convexity
• Computationally Related Problems
• Dominating sets for split and bipartite graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Graph theory
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• scientific article; zbMATH DE number 3359777 (Why is no real title available?)
• Introduction to algorithms.
• On geodetic sets formed by boundary vertices
• On the computation of the hull number of a graph
• On the hull number of some graph classes
• On the Optimal Solutions to AND/OR Series-Parallel Graphs
• Revisiting the complexity of and/or graph solution
• The Carathéodory number of the \(P_3\) convexity of chordal graphs
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory

Cited in

(5)

• On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• Using Barrier Graphs for Deadlock Prevention in Communication Networks
• Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs

This page was built for publication: And/or-convexity: a graph convexity based on processes and deadlock models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1639288)