On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
DOI10.1051/ITA:2001121zbMATH Open1014.68063OpenAlexW2071463666MaRDI QIDQ2773025FDOQ2773025
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics of discrete mathematics in relation to computer science (68R01) Approximation algorithms (68W25)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Approximating the minimum maximal independence number
- On approximating the minimum independent dominating set
- Structure in Approximation Classes
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- On domination problems for permutation and other graphs
- On the hardness of approximating minimization problems
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Approximate solution of NP optimization problems
- Zero knowledge and the chromatic number
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Independent domination in chordal graphs
- On Syntactic versus Computational Views of Approximability
- The achromatic number of a graph
- Domination in permutation graphs
- A new heuristic algorithm solving the linear ordering problem
- On the acyclic subgraph polytope
- Approximation algorithms for the achromatic number.
- On the computational complexity of upper fractional domination
- Maximum versus minimum invariants for graphs
- On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
Cited In (7)
- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
- In)approximability of Maximum Minimal FVS
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- (In)approximability of maximum minimal FVS
- On the Complexity Landscape of the Domination Chain
- Approximating Minimum Linear Ordering Problems
- On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
This page was built for publication: On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2773025)
