BibTeX database: published research of Andras Salamon
Version 1.07 of 2008-10-09
this file is available from http://www.gaon.net/andras/academic/azs.bib

@TECHREPORT{ Salamon1991:inherent,
	author = {Andr{\'a}s Salamon and Hanoch Neishlos},
	title = {Inherent Limitations on Parallel Program Performance},
	institution = {University of the Witwatersrand},
	year = {1991},
	number = {TR--1991--02},
	address = {Department of Computer Science, 2050 WITS, South Africa},
	month = may,
	url = {http://www.gaon.net/andras/academic/TR-Wits-CS-1991-2.pdf},
	alternate-url = {ftp://ftp.cs.wits.ac.za/pub/research/reports/TR-Wits-CS-1991-2.pdf},
	abstract = {
		We analyse the inherent performance of parallel
		software.  For this end we use a task graph to model
		software structure, and apply measures of performance
		based on the graph's execution time, given enough
		processors.  The task graph consists of tasks and
		precedence constraints between tasks: we show that
		performance cannot be improved by adding constraints
		to a task graph.  Using this we derive known bounds
		on performance in a systematic manner by comparing
		the structure of a program to benchmark structures for
		which performance can be easily determined.  Further,
		we simplify these bounds to highlight the importance of
		some summary parameters of the precedence structure.
		To conclude we examine an existing model of families
		of programs.  We find bounds on performance within
		a family and simplify them by restricting the family
		specification.	These bounds yield interesting insights
		into the scaled performance model of Gustafson,
		which models the effect of increasing the number of
		processors in tandem with program size.

	},
}

@TECHREPORT{ Salamon2001:task,
	author = {Andr{\'a}s Zolt{\'a}n Salamon},
	title = {Task Graph Performance Bounds Through Comparison Methods},
	institution = {Department of Computer Science, University of the
	Witwatersrand},
	year = {2001},
	month = jan,
	type = {Technical Report},
	number = {TR-Wits-CS-2001-0},
	url = {http://www.gaon.net/andras/academic/TR-Wits-CS-2001-0.pdf},
	alternate-url = {ftp://ftp.cs.wits.ac.za/pub/research/reports/TR-Wits-CS-2001-0.pdf},
	citeseer = {http://citeseer.ist.psu.edu/salamon01task.html},
	note = {(141 pages)},
	abstract = {
		When a parallel computation is represented in a
		formalism that imposes series-parallel structure on its
		task graph, it becomes amenable to automated analysis
		and scheduling.  Unfortunately, its execution time will
		usually also increase as precedence constraints are
		added to ensure series-parallel structure.  Bounding
		the slowdown ratio would allow an informed tradeoff
		between the benefits of a restrictive formalism and
		its cost in loss of performance.

		This dissertation deals with series-parallelising
		task graphs by adding precedence constraints to
		a task graph, to make the resulting task graph
		series-parallel.  The weak bounded slowdown conjecture
		for series-parallelising task graphs is introduced.
		This states that the slowdown is bounded if information
		about the workload can be used to guide the selection
		of which precedence constraints to add.  A theory
		of best series-parallelisations is developed to
		investigate this conjecture.  Partial evidence is
		presented that the weak slowdown bound is likely to
		be 4/3, and this bound is shown to be tight.

	},
}

@MASTERSTHESIS{ Salamon2001:thesis,
	author = {Andr{\'a}s Zolt{\'a}n Salamon},
	title = {Task Graph Performance Bounds Through Comparison Methods},
	school = {University of the Witwatersrand, Johannesburg},
	url = {http://www.gaon.net/andras/academic/TR-Wits-CS-2001-0.pdf},
	alternate-url = {ftp://ftp.cs.wits.ac.za/pub/research/reports/TR-Wits-CS-2001-0.pdf},
	year = {2001},
	month = jan,
}

@MISC{ Salamon2004:modulardecomp,
	author = {Andr{\'a}s Salamon},
	title = {Perl CPAN module Graph::ModularDecomposition},
	year = {2004--5},
	url = {http://www.gaon.net/dist/graph/},
	alternate-url = {http://search.cpan.org/~azs/Graph-ModularDecomposition-0.13/},
}

@MISC{ Salamon2005:liftutils,
	author = {Andr{\'a}s Salamon},
	title = {Perl module AI::Constraints::LiftUtils},
	year = {2005},
	url = {http://www.gaon.net/dist/lift/},
}

@MISC{ Salamon2007:complete,
	author = {Andr{\'a}s Salamon},
	title = {Complexity of complete constraint satisfaction problems},
	note = {Manuscript},
	year = {2007},
}

@InProceedings{ Salamon2008:perfect,
	author = {Andr{\'a}s Z. Salamon and Peter G. Jeavons},
	title = {Perfect Constraints Are Tractable},
	booktitle = {Proceedings of the 14th International Conference on
		Principles and Practice of Constraint Programming, {CP}
		2008, Sydney, Australia, 14--18 September},
	year = {2008},
	abstract = {
		By using recent results from graph theory, including
		the Strong Perfect Graph Theorem, we obtain a
		unifying framework for a number of tractable classes
		of constraint problems.  These include problems
		with chordal microstructure; problems with chordal
		microstructure complement; problems with tree
		structure; and the ``all-different'' constraint.
		In each of these cases we show that the associated
		microstructure of the problem is a perfect graph,
		and hence they are all part of the same larger family
		of tractable problems.

	},
}

@InProceedings{ Cooper2008:hybrid,
	author = {Martin C. Cooper and Peter G. Jeavons and
		Andr{\'a}s Z. Salamon},
	title = {Hybrid tractable {CSP}s which generalize tree
		structure},
	booktitle = {{ECAI} 2008, Proceedings of the 18th European
		Conference on Artificial Intelligence, July 21--25,
		Patras, Greece},
	series = {Frontiers in Artificial Intelligence and Applications},
	number = {178},
	publisher = {IOS Press},
	editor = {Malik Ghallab and Constantine D. Spyropoulos and Nikos
		Fakotakis and Nikos Avouris},
	issn = {0922-6389},
	isbn = {978-1-58603-891-5},
	year = {2008},
	pages = {530--534},
	abstract = {
		The constraint satisfaction problem (CSP)
		is a central generic problem in artificial
		intelligence. Considerable progress has been made
		in identifying properties which ensure tractability
		in such problems, such as the property of being
		tree-structured.  In this paper we introduce
		the broken-triangle property, which allows us to
		define a hybrid tractable class for this problem
		which significantly generalizes the class of
		problems with tree structure.  We show that the
		broken-triangle property is conservative (i.e.,
		it is preserved under domain reduction and hence
		under arc consistency operations) and that there is a
		polynomial-time algorithm to determine an ordering of
		the variables for which the broken-triangle property
		holds (or to determine that no such ordering exists).
		We also present a non-conservative extension of the
		broken-triangle property which is also sufficient to
		ensure tractability and can be detected in polynomial
		time.

	},
	accept = {121 full papers out of 518 submitted, best paper award},
}