TAILIEUCHUNG - Báo cáo toán học: "k-Colour partitions of acyclic tournaments"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: k-Colour partitions of acyclic tournaments. | k-Colour partitions of acyclic tournaments Paulo Barcia Universidade Nova de Lisboa Faculdade de Economia Campus de Campolide 1099-032 Lisboa Portugal barcia@ J. Orestes Cerdeira Instituto Superior de Agronomia Univ. Tecnica de Lisboa Tapada da Ajuda 1349-017 Lisboa Portugal orestes@ Submitted Jun 27 2002 Accepted Aug 21 2004 Published Jan 7 2005 Mathematics Subject Classifications 05C20 52B05 Abstract Let G1 be the acyclic tournament with the topological sort 0 1 2 n n 1 defined on node set N u 0 n 1 where N 1 2 . n . For integer k 2 let Gk be the graph obtained by taking k copies of every arc in G1 and colouring every copy with one of k different colours. A k-colour partition of N is a set of k paths from 0 to n 1 such that all arcs of each path have the same colour different paths have different colours and every node of N is included in exactly one path. If there are costs associated with the arcs of Gk the cost of a k-colour partition is the sum of the costs of its arcs. For determining minimum cost k-colour partitions we describe an O k2n2k algorithm and show this is an NP-hard problem. We also study the convex hull of the incidence vectors of k-colour partitions. We derive the dimension and establish a minimal equality set. For k 2 we identify a class of facet inducing inequalities. For k 2 we show that these inequalities turn out to be equations and that no other facet defining inequalities exists besides the trivial nonnegativity constraints. 1 Introduction Let G1 be the acyclic tournament with the topological sort 0 1 2 n n 1 dehned on node set N u 0 n 1 where N 1 2 . n . The arcs of G1 are therefore the pairs i j with i j. Given an integer k 2 consider the di graph Gk obtained by This author s research was financially supported by the Portuguese Foundation for Science and Technology FCT THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R5 1 taking k copies of every arc in G1 and colouring every copy with one of k different colours. A .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.