Backup 2-center on interval graphs

DOI10.1016/J.TCS.2012.05.003MaRDI QIDQ442280zbMATH OpenOpenAlexFDO

Authors Yanmei Hong, Liying Kang

Publication date 10 August 2012

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

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

zbMATH Keywords

interval graphbackup 2-center

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07)

Recommendations

• A simple linear-time algorithm for computing the center of an interval graph
• The backup 2-median problem on block graphs
• Back-up 2-center on a path/tree/cycle/unicycle
• The backup 2‐center and backup 2‐median problems on trees
• Interval Graph Problems on Reconfigurable Meshes

Cites work

• scientific article; zbMATH DE number 177557 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A fully dynamic graph algorithm for recognizing interval graphs
• A linear-time algorithm for solving the center problem on weighted cactus graphs
• A simple linear-time algorithm for computing the center of an interval graph
• Algorithms and Computation
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Overview of Representative Problems in Location Research
• An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths
• Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
• Efficient algorithms for centers and medians in interval and circular-arc graphs
• Finding kth paths and p-centers by generating and searching good data structures
• New Results on the Complexity of p-Centre Problems
• On some optimization problems on \(k\)-trees and partial \(k\)-trees
• Parallel concepts in graph theory
• Proper interval graphs and the guard problem
• Scheduling with conflicts on bipartite and interval graphs
• Slowing down sorting networks to obtain faster sorting algorithms
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The backup 2‐center and backup 2‐median problems on trees
• The obnoxious center problem on weighted cactus graphs.

Cited in

(3)

• Embeddings into almost self-centered graphs of given radius
• Backup multifacility location problem with \(l_p\) norm
• An optimal algorithm for the weighted backup 2-center problem on a tree

This page was built for publication: Backup 2-center on interval graphs

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