Optimizing concurrency under Scheduling by Edge Reversal
DOI10.1002/net.22014zbMath1529.68221MaRDI QIDQ6087133
Unnamed Author, Luérbio Faria, Unnamed Author, Luidi Simonetti, Felipe M. G. França, Abilio Lucena
Publication date: 11 December 2023
Published in: Networks (Search for Journal in Brave)
schedulingdistributed systemsapproximationNP-completenesscoloringconcurrencylongest cycleedge reversal
Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- On approximating the longest path in a graph
- A lower bound on the period length of a distributed scheduler
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Three short proofs in graph theory
- Some simplified NP-complete graph problems
- Every planar map is four colorable. I: Discharging
- The multichromatic numbers of some Kneser graphs
- Long directed \((s,t)\)-path: FPT algorithm
- Searching and pebbling
- NP-hardness of shop-scheduling problems with three jobs
- Parameterized edge Hamiltonicity
- Recognizing Berge graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Algorithmic Composition
- Complexity of network synchronization
- Efficient Planarity Testing
- The Planar Hamiltonian Circuit Problem is NP-Complete
- On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Node-and edge-deletion NP-complete problems
- Parameterized Algorithms
- Principles of Distributed Systems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Optimizing concurrency under Scheduling by Edge Reversal
