On spanning galaxies in digraphs

DOI10.1016/j.dam.2011.07.013zbMath1241.05043OpenAlexW2033391704MaRDI QIDQ415275

Frédéric Havet, Alexandre Pinlou, Daniel Gonçalves, Steéphan Thomassé

Publication date: 11 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.07.013

zbMATH Keywords

algorithmsfixed parameter tractabledirected star arboricityeven strong subdigraphspanning galaxy

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

Finding good 2-partitions of digraphs. II. Enumerable properties ⋮ Bounds on directed star arboricity in some digraph classes

Cites Work

• Unnamed Item
• Even cycles in directed graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• On incidence coloring and star arboricity of graphs
• Pólya's permanent problem
• The star arboricity of graphs
• Permanents, Pfaffian orientations, and even directed circuits
• WDM and Directed Star Arboricity
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Digraphs