And/or-convexity: a graph convexity based on processes and deadlock models
From MaRDI portal
Publication:1639288
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
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
