Layered graphs: applications and algorithms

DOI10.3390/A11070093MaRDI QIDQ2287476zbMATH OpenOpenAlexWikidataFDO

Authors Bhadrachalam Chitturi, Srijith Balachander, Sandeep Satheesh, Krithic Puthiyoppil

Publication date 21 January 2020

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a11070093

zbMATH Keywords

dynamic programmingdominating setNP-completenessindependent setvertex coverlayered graphquasi-polynomial timestring transformations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• On dominating set of some subclasses of string graphs
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• On the parameterized complexity of layered graph drawing
• scientific article; zbMATH DE number 468640
• Serial and parallel algorithms for \((k,2)\)-partite graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A linear algorithm for the domination number of a tree
• A note on complexity of genetic mutations
• Adjacent Swaps on Strings
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms for maximum independent sets
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• An optimal time algorithm for finding a maximum weight independent set in a tree
• Approximation algorithms for NP-complete problems on planar graphs
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• Dominating sets for split and bipartite graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Finding a Maximum Independent Set
• Graph theory with applications
• Linear-time computability of combinatorial problems on series-parallel graphs
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• On maximal independent sets of vertices in claw-free graphs
• On the maximum independent set problem in subclasses of planar graphs
• Reducibility among combinatorial problems
• Solving connected dominating set faster than \(2^n\)
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The complexity of comparability graph recognition and coloring

Cited in

(5)

• Width-restricted layering of acyclic digraphs with consideration of dummy nodes
• Traversing Layered Graphs Using the Work Function Algorithm
• Layered graph approaches for combinatorial optimization problems
• Graph layouts via layered separators
• Multilist layering: Complexity and applications

This page was built for publication: Layered graphs: applications and algorithms

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