2012-03-01, English, Article, Report edition: Enumerating homomorphisms.(Report) Bulatov, Andrei A.; Dalmau, ViCtor; Grohe, Martin; ...

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/176176273
Physical Description
  • Report
  • Magazine/​Journal article
Published
  • Elsevier B.V., 2012 March
Language
  • English

Edition details

Title
  • Enumerating homomorphisms.(Report)
Also Titled
  • Enumerating homomorphisms.
Appears In
  • Journal of Computer and System Sciences, v.78, no.2, 2012 March, p.638(13) (ISSN: 0022-0000)
Author
  • Bulatov, Andrei A.
  • Dalmau, ViCtor
  • Grohe, Martin
  • Marx, DaNiel
Published
  • Elsevier B.V., 2012 March
Physical Description
  • Report
  • Magazine/​Journal article
Subjects
Target Audience
  • Academic
Summary
  • To link to full-text access for this article, visit this link: http:/​/​dx.doi.org/​10.1016/​j.jcss.2011.09.006 Byline: Andrei A. Bulatov (a), Victor Dalmau (b), Martin Grohe (c), Daniel Marx (c)(d) Keywords: Enumeration; Computational complexity; Homomorphisms; Constraint satisfaction Abstract: The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay. Author Affiliation: (a) School of Computing Science, Simon Fraser University, Burnaby, Canada (b) Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain (c) Institut fur Informatik, Humboldt-Universitat, Berlin, Germany (d) Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary Article History: Received 2 February 2011; Revised 6 September 2011; Accepted 20 September 2011 Article Note: (footnote) [star] A preliminary version of this paper was published in the proceedings of STACSE1/409.
Terms of Use
  • COPYRIGHT 2012 Elsevier B.V.
Language
  • English
Database
  • Gale Academic OneFile
Identifier
  • 277727793

Get this edition

Via a library membership

Library View online via
Australian Bureau of Statistics. Castles Library.
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University. Document Supply Service.
Australian Institute of Professional Education.
Australian Lutheran College. Lohe Memorial Library.
Australian School of Management. Perth Campus Library.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
University of Adelaide. Barr Smith Library.
Blue Mountains International Hotel Management School.
Bond University. John and Alison Kearney Library .
Campion College Australia.
Charles Darwin University. Casuarina Campus Library.
Cengage Education.
Christian Heritage College. Christian Heritage College Library.
Deakin University. Deakin University Library.
Edith Cowan University. Edith Cowan University Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
University of Notre Dame Australia. Galvin Medical Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Moore Theological College. Moore Theological College Library.
SA Mental Health Services.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
South Western Sydney Institute of TAFE.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Tabor Adelaide. Tabor College Library.
The Southport School. Senior Library.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Canberra. University of Canberra Library.
University of Wollongong. University of Wollongong Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Australian Bureau of Statistics. Castles Library.
University of Canberra. University of Canberra Library.
Show 0 more libraries...
Library View online via
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University. Document Supply Service.
Australian Institute of Professional Education.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
Blue Mountains International Hotel Management School.
Campion College Australia.
Cengage Education.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Moore Theological College. Moore Theological College Library.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Western Sydney Institute of TAFE.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Wollongong. University of Wollongong Library.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Charles Darwin University. Casuarina Campus Library.
Show 0 more libraries...
Library View online via
Bond University. John and Alison Kearney Library .
Christian Heritage College. Christian Heritage College Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
The Southport School. Senior Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Show 0 more libraries...
Library View online via
Australian Lutheran College. Lohe Memorial Library.
University of Adelaide. Barr Smith Library.
SA Mental Health Services.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
Tabor Adelaide. Tabor College Library.
Show 0 more libraries...
Library View online via
Deakin University. Deakin University Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Show 0 more libraries...

With access conditions

Published in

Some editions of the publication "Journal of computer and system sciences" are available from these libraries. The edition containing this article ( v.78, no.2, 2012 March, p.638(13) ) may not be available:

None of your libraries hold this item.

These 15 locations in All:

Library Access Call number(s) Formats held Language
CAVAL. CARM Centre. May not be open to the public brn.293430; Held; Vol. 1, no. 1 - v. 49, no. 3; Mar. 1967 - Dec. 1994; Inc. Periodical; Journal, magazine, other English
Charles Sturt University. Bathurst Campus Library. Open to the public 000099127; P001.64/6; Vol.7, no.1 (Feb. 1973)- v.23, no.3 (Dec. 1981) Periodical; Journal, magazine, other English
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 002052103; Full Text Available; Elsevier SD Freedom Collection - Available from 1996 volume: 52 issue: 1 Periodical; Journal, magazine, other English
Defence Science and Technology Group. DST Group Research Information Services - Melbourne. Not open to the public Serials; Vol. 1, no. 1-v. 63, no. 4; Mar. 1967-Dec. 2001; Incomp. Lacks vol. 7, no. 3, v. 28, no. 3, v. 29, no. 3, v. 63, no. 3 Periodical; Journal, magazine, other English
Edith Cowan University. Edith Cowan University Library. Open to the public Periodical; Journal, magazine, other English
Griffith University. Griffith University Library. Open to the public .b13511786; Electronic Resource : Publ. may restrict Doc. Del. Periodical; Journal, magazine, other English
James Cook University. Townsville Campus Library. Open to the public 471676; <471676> Periodical; Journal, magazine, other English
Monash University. Monash University Library. Open to the public 9928821401751; 510.7805 J86; v. 50 (1995) to v. 65 (2002); HA; SER Periodical; Journal, magazine, other English
National Library of Australia. Open to the public S 001.6405 JOU; Vol. 8, no. 1-v. 51, no. 3; Feb. 1974-Dec. 1995 Periodical; Journal, magazine, other English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Periodical; Journal, magazine, other English
The University of Melbourne. The University of Melbourne Library. Open to the public Ba P 001.605 J86; v.1-v.67; 1967-2003 Periodical; Journal, magazine, other English
University of Newcastle. University of Newcastle Library. Open to the public 510.7805/4; v.1,no.1-v.30,no.1; Apr.1967-Feb.1985 Periodical; Journal, magazine, other English
University of Queensland. University of Queensland Library. Open to the public b10152283; eslp QA76.5 .J7 : 2(1968)-49(1994) Periodical; Journal, magazine, other English
University of Western Australia. University of Western Australia Library. Open to the public 9942678902101; HELD; V. 5-49, 50(1) ; 1971-1995. Periodical; Journal, magazine, other English
Western Sydney University. Penrith Campus Library. Open to the public 399747; Online version Periodical; Journal, magazine, other English
Show 0 more libraries...

This single location in Australian Capital Territory:

Library Access Call number(s) Formats held Language
National Library of Australia. Open to the public S 001.6405 JOU; Vol. 8, no. 1-v. 51, no. 3; Feb. 1974-Dec. 1995 Periodical; Journal, magazine, other English
Show 0 more libraries...

These 5 locations in New South Wales:

Library Access Call number(s) Formats held Language
Charles Sturt University. Bathurst Campus Library. Open to the public 000099127; P001.64/6; Vol.7, no.1 (Feb. 1973)- v.23, no.3 (Dec. 1981) Periodical; Journal, magazine, other English
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 002052103; Full Text Available; Elsevier SD Freedom Collection - Available from 1996 volume: 52 issue: 1 Periodical; Journal, magazine, other English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Periodical; Journal, magazine, other English
University of Newcastle. University of Newcastle Library. Open to the public 510.7805/4; v.1,no.1-v.30,no.1; Apr.1967-Feb.1985 Periodical; Journal, magazine, other English
Western Sydney University. Penrith Campus Library. Open to the public 399747; Online version Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

These 3 locations in Queensland:

Library Access Call number(s) Formats held Language
Griffith University. Griffith University Library. Open to the public .b13511786; Electronic Resource : Publ. may restrict Doc. Del. Periodical; Journal, magazine, other English
James Cook University. Townsville Campus Library. Open to the public 471676; <471676> Periodical; Journal, magazine, other English
University of Queensland. University of Queensland Library. Open to the public b10152283; eslp QA76.5 .J7 : 2(1968)-49(1994) Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.
None of your libraries hold this item.

These 4 locations in Victoria:

Library Access Call number(s) Formats held Language
CAVAL. CARM Centre. May not be open to the public brn.293430; Held; Vol. 1, no. 1 - v. 49, no. 3; Mar. 1967 - Dec. 1994; Inc. Periodical; Journal, magazine, other English
Defence Science and Technology Group. DST Group Research Information Services - Melbourne. Not open to the public Serials; Vol. 1, no. 1-v. 63, no. 4; Mar. 1967-Dec. 2001; Incomp. Lacks vol. 7, no. 3, v. 28, no. 3, v. 29, no. 3, v. 63, no. 3 Periodical; Journal, magazine, other English
Monash University. Monash University Library. Open to the public 9928821401751; 510.7805 J86; v. 50 (1995) to v. 65 (2002); HA; SER Periodical; Journal, magazine, other English
The University of Melbourne. The University of Melbourne Library. Open to the public Ba P 001.605 J86; v.1-v.67; 1967-2003 Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

Other suppliers

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment