Backup 2-center on interval graphs

DOI10.1016/J.TCS.2012.05.003zbMATH Open1243.68023OpenAlexW2046119322MaRDI QIDQ442280FDOQ442280

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

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

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)

Cites Work

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

Cited In (3)

• Backup multifacility location problem with \(l_p\) norm
• Embeddings into almost self-centered graphs of given radius
• 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)