@article{ambuhl_single_2008,
	title = {Single {Machine} {Precedence} {Constrained} {Scheduling} {Is} a {Vertex} {Cover} {Problem}},
	volume = {53},
	issn = {0178-4617, 1432-0541},
	url = {http://link.springer.com/article/10.1007/s00453-008-9251-6},
	doi = {10.1007/s00453-008-9251-6},
	abstract = {In this paper we study the single machine precedence constrained scheduling problem of minimizing the sum of weighted completion time. Specifically, we settle an open problem first raised by Chudak and Hochbaum and whose answer was subsequently conjectured by Correa and Schulz. As shown by Correa and Schulz, the proof of this conjecture implies that the addressed scheduling problem is a special case of the vertex cover problem. This means that previous results for the scheduling problem can be explained, and in some cases improved, by means of vertex cover theory. For example, the conjecture implies the existence of a polynomial time algorithm for the special case of two-dimensional partial orders. This considerably extends Lawler’s result from 1978 for series-parallel orders.},
	language = {en},
	number = {4},
	urldate = {2015-04-29TZ},
	journal = {Algorithmica},
	author = {Ambühl, Christoph and Mastrolilli, Monaldo},
	month = nov,
	year = {2008},
	keywords = {Algorithm Analysis and Problem Complexity, Computer Systems Organization and Communication Networks, Data Structures, Cryptology and Information Theory, Mathematics of Computing, Theory of Computation, Vertex cover, algorithms, scheduling},
	pages = {488--503}
}

{"_id":"5zbozAXSnW7MFc4b6","bibbaseid":"ambhl-mastrolilli-singlemachineprecedenceconstrainedschedulingisavertexcoverproblem-2008","downloads":0,"creationDate":"2016-12-19T20:50:58.217Z","title":"Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem","author_short":["Ambühl, C.","Mastrolilli, M."],"year":2008,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem","volume":"53","issn":"0178-4617, 1432-0541","url":"http://link.springer.com/article/10.1007/s00453-008-9251-6","doi":"10.1007/s00453-008-9251-6","abstract":"In this paper we study the single machine precedence constrained scheduling problem of minimizing the sum of weighted completion time. Specifically, we settle an open problem first raised by Chudak and Hochbaum and whose answer was subsequently conjectured by Correa and Schulz. As shown by Correa and Schulz, the proof of this conjecture implies that the addressed scheduling problem is a special case of the vertex cover problem. This means that previous results for the scheduling problem can be explained, and in some cases improved, by means of vertex cover theory. For example, the conjecture implies the existence of a polynomial time algorithm for the special case of two-dimensional partial orders. This considerably extends Lawler’s result from 1978 for series-parallel orders.","language":"en","number":"4","urldate":"2015-04-29TZ","journal":"Algorithmica","author":[{"propositions":[],"lastnames":["Ambühl"],"firstnames":["Christoph"],"suffixes":[]},{"propositions":[],"lastnames":["Mastrolilli"],"firstnames":["Monaldo"],"suffixes":[]}],"month":"November","year":"2008","keywords":"Algorithm Analysis and Problem Complexity, Computer Systems Organization and Communication Networks, Data Structures, Cryptology and Information Theory, Mathematics of Computing, Theory of Computation, Vertex cover, algorithms, scheduling","pages":"488--503","bibtex":"@article{ambuhl_single_2008,\n\ttitle = {Single {Machine} {Precedence} {Constrained} {Scheduling} {Is} a {Vertex} {Cover} {Problem}},\n\tvolume = {53},\n\tissn = {0178-4617, 1432-0541},\n\turl = {http://link.springer.com/article/10.1007/s00453-008-9251-6},\n\tdoi = {10.1007/s00453-008-9251-6},\n\tabstract = {In this paper we study the single machine precedence constrained scheduling problem of minimizing the sum of weighted completion time. Specifically, we settle an open problem first raised by Chudak and Hochbaum and whose answer was subsequently conjectured by Correa and Schulz. As shown by Correa and Schulz, the proof of this conjecture implies that the addressed scheduling problem is a special case of the vertex cover problem. This means that previous results for the scheduling problem can be explained, and in some cases improved, by means of vertex cover theory. For example, the conjecture implies the existence of a polynomial time algorithm for the special case of two-dimensional partial orders. This considerably extends Lawler’s result from 1978 for series-parallel orders.},\n\tlanguage = {en},\n\tnumber = {4},\n\turldate = {2015-04-29TZ},\n\tjournal = {Algorithmica},\n\tauthor = {Ambühl, Christoph and Mastrolilli, Monaldo},\n\tmonth = nov,\n\tyear = {2008},\n\tkeywords = {Algorithm Analysis and Problem Complexity, Computer Systems Organization and Communication Networks, Data Structures, Cryptology and Information Theory, Mathematics of Computing, Theory of Computation, Vertex cover, algorithms, scheduling},\n\tpages = {488--503}\n}\n\n","author_short":["Ambühl, C.","Mastrolilli, M."],"key":"ambuhl_single_2008","id":"ambuhl_single_2008","bibbaseid":"ambhl-mastrolilli-singlemachineprecedenceconstrainedschedulingisavertexcoverproblem-2008","role":"author","urls":{"Paper":"http://link.springer.com/article/10.1007/s00453-008-9251-6"},"keyword":["Algorithm Analysis and Problem Complexity","Computer Systems Organization and Communication Networks","Data Structures","Cryptology and Information Theory","Mathematics of Computing","Theory of Computation","Vertex cover","algorithms","scheduling"],"downloads":0,"html":""},"search_terms":["single","machine","precedence","constrained","scheduling","vertex","cover","problem","ambühl","mastrolilli"],"keywords":["algorithm analysis and problem complexity","computer systems organization and communication networks","data structures","cryptology and information theory","mathematics of computing","theory of computation","vertex cover","algorithms","scheduling"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}