<%@ page language="java" contentType="text/html" %>
<%-- Include common initialisation code --%>
<%@ include file="/arch/common.jsp" %>
<%-- The current tab --%>
<% String currentTab = "Research"; %>
<%-- Content of navigation pane --%>
<%@ include file="nav.jsp" %>
<% showCurrentLink=true; %>
<%-- Current navigation location --%>
<% String currentNav = "Reports and Theses"; %>
<%-- Include the code for the document header --%>
<%@ include file="/arch/header.jsp" %>
Research Report CS-RR-364
<%-- Include the code for the lines and navigation --%>
<%@ include file="/arch/middle.jsp" %>
Leslie Ann Goldberg and Mark Jerrum,
Counting Unlabelled Subrees of a Tree is #P-complete
(November 26, 1999).
Abstract
The problem of counting unlabelled subtrees of a tree (i.e., subtrees
that are distinct up to isomorphism) is #P-complete, and hence equivalent
in computational difficulty to evaluating the permanent of a 0,1-matrix.
Download
cs-rr-364.ps.gz
<%-- Include the code for the document footer --%>
<%@ include file="/arch/footer.jsp" %>