On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem

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

zbMATH Keywords

NP-optimization problemsminimum linear ordering problem

Mathematics Subject Classification ID

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