Compact Forbidden-Set Routing

DOI10.1007/978-3-540-70918-3_4MaRDI QIDQ3590921zbMATH OpenOpenAlexFDO

Authors Andrew Twigg, Bruno Courcelle

Publication date 3 September 2007

Published in STACS 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70918-3_4

zbMATH Keywords

compact routinglabelling schemes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Constrained-path labellings on graphs of bounded clique-width
• On interval routing schemes and treewidth
• Algorithms and Computation
• Distributed Computing
• On compact and efficient routing in certain graph classes

Cited in

(20)

• Labelling and Implicit Routing in Networks
• Fault-Tolerant Compact Routing Schemes for General Graphs
• \(f\)-sensitivity distance oracles and routing schemes
• On a disparity between relative cliquewidth and relative NLC-width
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• Constrained-path labellings on graphs of bounded clique-width
• Deterministic fault-tolerant connectivity labeling scheme
• Fault-tolerant distance labeling for planar graphs
• Restorable shortest path tiebreaking for edge-faulty graphs
• Efficient First-Order Model-Checking Using Short Labels
• Graph operations characterizing rank-width
• Connectivity check in 3-connected planar graphs with obstacles
• A note on models for graph representations
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• Inductive computations on graphs defined by clique-width expressions
• Compact routing messages in self-healing trees
• Connectivity labeling in faulty colored graphs
• Efficient oracles and routing schemes for replacement paths
• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)

This page was built for publication: Compact Forbidden-Set Routing

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