Complexity and approximability of the marking problem

MaRDI QIDQ5163006zbMATH OpenFDO

Authors Mohammad M. Valizadeh, M. H. Tadayon

Publication date 8 November 2021

Full work available at URL https://www.ijmex.com/index.php/ijmex/article/view/1443

zbMATH Keywords

approximabilitycomplexityfeasibilitymarking problemreachability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On a DAG partitioning problem
• Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem
• Computational complexity of the graph approximation problem
• The Maximum Labeled Path Problem
• On the hardness of finding near-optimal multicuts in directed acyclic graphs

Cites work

• 2‐Banach Spaces
• Banach-Steinhaus theorems for bounded linear operators with values in a generalized 2-normed space
• Convexity and optimization in Banach spaces.
• Hahn-Banach theorem in generalized 2-normed spaces
• scientific article; zbMATH DE number 1807400 (Why is no real title available?)
• scientific article; zbMATH DE number 5296576 (Why is no real title available?)
• scientific article; zbMATH DE number 5382104 (Why is no real title available?)
• scientific article; zbMATH DE number 3964706 (Why is no real title available?)
• scientific article; zbMATH DE number 3975612 (Why is no real title available?)
• scientific article; zbMATH DE number 3455914 (Why is no real title available?)
• scientific article; zbMATH DE number 624799 (Why is no real title available?)
• scientific article; zbMATH DE number 1956204 (Why is no real title available?)
• Isosceles Orthogonal Triples in Linear 2‐Normed Spaces
• Linear operators on generalized 2-normed spaces
• Lineare 2‐normierte Räume
• On 2-normed sets
• On isometries of normed linear spaces
• On maps that preserve orthogonality in normed spaces
• Operators preserving orthogonality are isometries
• Orthogonalities and functional equations

Cited in

(2)

• scientific article; zbMATH DE number 4156195 (Why is no real title available?)
• Dörfler marking with minimal cardinality is a linear complexity problem

This page was built for publication: Complexity and approximability of the marking problem

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