Algorithms for finding maximum transitive subtournaments

DOI10.1007/S10878-014-9788-ZMaRDI QIDQ5963652zbMATH OpenOpenAlexFDO

Authors Lasse Kiviluoto, Patric R. J. Östergård, Vesa Vaskelainen

Publication date 23 February 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-014-9788-z

zbMATH Keywords

backtrack searchcliquedirected acyclic graphfeedback vertex setRussian doll searchtransitive tournament

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Coloring the edges of a directed graph
• The complexity of finding certain trees in tournaments
• Some extremal properties concerning transitivity in graphs
• Coloring the nodes of a directed graph
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs

Cites work

• A fast algorithm for the maximum clique problem
• A polyhedral approach to the feedback vertex set problem
• An exact algorithm for the maximum clique problem
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Clique-detection models in computational biochemistry and genomics
• Exact computation of minimum feedback vertex sets with relational algebra
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 4096245 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• Local chromatic number and Sperner capacity
• On locating minimum feedback vertex sets
• On the capacity of digraphs
• Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities
• Qualitative independence and Sperner problems for directed graphs
• Reducibility among combinatorial problems
• Russian doll search for the Steiner triple covering problem
• Sperner capacity of small digraphs
• The dichromatic number of a digraph
• The maximum clique problem

Cited in

(5)

• Coloring the edges of a directed graph
• An optimal algorithm for finding all convex subsets in tournaments
• Design, implementation, and analysis of maximum transversal algorithms
• Coloring the nodes of a directed graph
• A tournament of order 14 with disjoint Banks and Slater sets

Describes a project that uses

Uses Software

• CLIP

This page was built for publication: Algorithms for finding maximum transitive subtournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963652)