<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Computing an Evolutionary Ordering is Hard

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Dec 2015Embargo end date: 01 Jan 2014 France English Publisher:Elsevier BVJournal:Electronic Notes in Discrete Mathematics, volume 50, pages 255-260 (issn: 1571-0653,

Authors: Blerina Sinaimeri; Blerina Sinaimeri; Laurent Bulteau; Laurent Bulteau; Gustavo Sacomoto; Gustavo Sacomoto;

doi: 10.1016/j.endm.2015.07.043 , 10.48550/arxiv.1410.6663

arXiv: http://arxiv.org/abs/1410.6663

Computing an Evolutionary Ordering is Hard

- Summary
- Subjects
- Related research
  (1)
- Metrics

Abstract

We prove that computing an evolutionary ordering of a family of sets, i.e. an ordering where each set intersects with --but is not included in-- the union earlier sets, is NP-hard.

Country

France

Related Organizations

French National Centre for Scientific Research
France
French Institute for Research in Computer Science and Automation
France
University of Nantes
France
Inria Grenoble - Rhône-Alpes research centre
France
Biometry and Evolutionary Biology Laboratory
France

View all View all

Keywords

FOS: Computer and information sciences, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ear-decomposition, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computational Complexity (cs.CC), 004, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Computational Complexity, evolutionary family, complexity

1 Research products, page of 1

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average