On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
type: Item
instance of: scholarly article
zbMATH Open document ID: 1014.68063
author: Sounaka Mishra
author: Kripasindhu Sikdar
publication date: 2002-02-20T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/222064
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R01
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 1709146
zbMATH Keywords: minimum linear ordering problem
zbMATH Keywords: NP-optimization problems
MaRDI profile type: Publication
OpenAlex ID: W2071463666
cites work: Approximate solution of NP optimization problems
cites work: Q4258216
cites work: The algorithmic use of hypertree structure and maximum neighbourhood orderings
cites work: On domination problems for permutation and other graphs
cites work: A new heuristic algorithm solving the linear ordering problem
cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
cites work: Approximation algorithms for the achromatic number.
cites work: On the computational complexity of upper fractional domination
cites work: Structure in Approximation Classes
cites work: Zero knowledge and the chromatic number
cites work: Independent domination in chordal graphs
cites work: Domination in permutation graphs
cites work: A Cutting Plane Algorithm for the Linear Ordering Problem
cites work: On the acyclic subgraph polytope
cites work: Q5572939
cites work: Maximum versus minimum invariants for graphs
cites work: The achromatic number of a graph
cites work: Approximating the minimum maximal independence number
cites work: On approximating the minimum independent dominating set
cites work: Q4764626
cites work: On Syntactic versus Computational Views of Approximability
cites work: On the hardness of approximating minimization problems
cites work: Optimization, approximation, and complexity classes
cites work: Q3737461
cites work: Q4536425
cites work: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
DOI: 10.1051/ITA:2001121
title: On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
published in: RAIRO. Theoretical Informatics and Applications
description: scientific article; zbMATH DE number 1709146