On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
From MaRDI portal
Publication:2773025
DOI10.1051/ita:2001121zbMath1014.68063OpenAlexW2071463666MaRDI QIDQ2773025
Kripasindhu Sikdar, Sounaka Mishra
Publication date: 20 February 2002
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2001__35_3_287_0
General topics of discrete mathematics in relation to computer science (68R01) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (5)
Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ In)approximability of Maximum Minimal FVS ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ On the Complexity Landscape of the Domination Chain ⋮ (In)approximability of maximum minimal FVS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximate solution of NP optimization problems
- Approximating the minimum maximal independence number
- On approximating the minimum independent dominating set
- On the computational complexity of upper fractional domination
- On domination problems for permutation and other graphs
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Independent domination in chordal graphs
- Optimization, approximation, and complexity classes
- Zero knowledge and the chromatic number
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- A new heuristic algorithm solving the linear ordering problem
- On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
- Approximation Algorithms for the Achromatic Number
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Maximum versus minimum invariants for graphs
- On the acyclic subgraph polytope
- Domination in permutation graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- On Syntactic versus Computational Views of Approximability
- Structure in Approximation Classes
- On the hardness of approximating minimization problems
- The achromatic number of a graph
This page was built for publication: On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
