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

DOI10.1007/s10479-017-2666-1zbMath1388.05050OpenAlexW2764281430MaRDI QIDQ1639288

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

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

graph convexityand/or graphsdeadlockAND-OR model

Mathematics Subject Classification ID

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

Related Items

A general framework for path convexities ⋮ Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs ⋮ \(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 ⋮ On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem

Cites Work

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