Realization problems on reachability sequences

DOI10.1016/J.TCS.2021.02.034MaRDI QIDQ5925515zbMATH OpenOpenAlexFDO

Authors Matthew Dippel, Ravi Sundaram, Akshar Varma

Publication date 14 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.02.034

zbMATH Keywords

bicriteria approximationgraph realizationreachability sequencesstrong NP-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Realization problems on reachability sequences
• Dag realizations of directed degree sequences
• scientific article; zbMATH DE number 970793

Cites work

• `` Strong NP-Completeness Results
• A congruence theorem for trees
• A note on the characterization of digraphic sequences
• A remark on the existence of finite graphs
• A survey and annotated bibliography of multiobjective combinatorial optimization
• Adaptive hierarchical clustering using ordinal queries
• Approximating the k-set packing problem by local improvements
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Dag realizations of directed degree sequences
• Eccentric sequences and eccentric sets in graphs
• Eccentric sequences in graphs
• Graph profile realizations and applications to social networks
• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• scientific article; zbMATH DE number 3458693 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3258862 (Why is no real title available?)
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• On reconstructing graphs from their sets of subgraphs
• On Reconstruction of Matrices
• On the problem of reconstructing a tournament from subtournaments
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Powers of tensors and fast matrix multiplication
• Realizability and uniqueness in graphs
• Realizability of graph specifications: characterizations and algorithms
• Reconstructibility of trees from subtree size frequencies
• Reconstruction from subsequences.
• Reconstruction of locally finite connected graphs with at least three infinite wings
• Reconstruction of rooted trees from subtrees
• Reconstruction of Trees
• Sorting and selection in posets
• String reconstruction from substring compositions
• The complexity of reconstructing trees from qualitative characters and subtrees
• The probabilistic method

Cited in

(2)

• Dag realizations of directed degree sequences
• Realization problems on reachability sequences

This page was built for publication: Realization problems on reachability sequences

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