University of Bergen : Fac. Math and Nat. Sci. : Department of Informatics : Spectrum


Publications

Go to:

Spectrum home page

2007:

  1. F. Manne, S. Wang, and Q. Xin, Faster Radio Broadcasting in Planar Graphs, Accepted for publication in Journal of Networks.
  2. F. Cicalese, F. Manne, and Q. Xin Faster Centralized Communication in Radio Networks, Accepted for publication in Algorithmica.
  3. J.Fiala, D.Paulusma and J.A.Telle, Locally constrained graph homomorphisms and equitable partitions, Accepted for publication in European Journal of Combinatorics.
  4. Q. Xin, Faster Treasure Hunts, and Better Strongly Universal Exploration Sequences, Proceedings of the 18th International Symposium on Algorithms and Computation}, ISAAC 2007, Springer LNCS, to appear.
  5. F. Manne and M. Mjelde A Self-Stabilizing Weighted Matching Algorithm To appear in proceedings of SSS 2007, Springer LNCS.
  6. T.Herman, S.Pemmaraju, L.Pilard and M.Mjelde. Temporal Partition in Sensor Networks. To appear in proceedings of SSS 2007, Springer LNCS.
  7. D.Yuan, J.Bauer, and D.Haugland, Minimum-energy broadcast and multicast in wireless networks: An integer programming approach and improved heuristic algorithms, accepted for publication in Ad Hoc Networks.
  8. J.Bauer, D.Haugland, and D.Yuan, Analysis and Computational Study of Several Integer Programming Formulations for Minimum-Energy Multicasting in Wireless Ad Hoc Networks, accepted for publication in Networks, 2007.
  9. F.Manne, M.Mjelde, L.Pilard, and S.Tixeuil, A New Self-Stabilizing Maximal Matching Algorithm In Springer LNCS 4474, pp. 96 -108, 2007.
  10. D. Haugland, A Bidirectional Greedy Heuristic for the Subspace Selection Problem, in T.StŘtzle, M.Birattari, H.H.Hoos (Eds): SLS 2007, LNCS 4638, pp. 162-176, 2007.
  11. F. Fomin, P. Heggernes, D. Kratsch, Exact algorithms for graph homomorphism Theory of Computing Systems 41-2, pp. 381-393, 2007.
  12. L. Gasieniec, I. Potapov, and Q. Xin, Time efficient centralized gossiping in radio networks, Theoretical Computer Science 383 (1): pp. 45-58, 2007.
  13. L. Gasieniec, D. Peleg and Q. Xin, Faster Communication in Known Topology Radio Networks Distributed Computing, 19 (4): 289-300 (2007).
  14. L. Gasieniec, C. Su, P. Wong and Q. Xin, Routing via Single-source and Multiple-source Queries in Static Sensor Networks, Journal of Discrete Algorithms, 5 (1): 1-11 (2007)
  15. F. Manne, S. Wang, and Q. Xin, Faster Radio Broadcasting in Planar Graphs proceedings of the 4th Annual Conference on Wireless On demand Network Systems and Services,} WONS 2007, IEEE press, pp. 9--13

2006:

  1. P.Heggernes and D.Lokshtanov Optimal broadcast domination in polynomial time, Discrete Mathematics 306-24 (2006), pages 3267-3280.
  2. L. Gasieniec, E. Kranakis A. Pelc and Q. Xin, Deterministic M2M Multicast in Radio Networks Theoretical Computer Science 362 (1-3): 196-206 (2006)
  3. D.Wood and J.A.Telle Planar decompositions and the crossing number of graphs with an excluded minor Proceedings GD'06, Graph Drawing 2006, LNCS 4372, pp.150-161.
  4. C.Sloper and J.A.Telle Towards a taxonomy of techniques for designing parameterized algorithms Proceedings IWPEC'06, International Workshop on Parameterized and Exact Computation, LNCS 4169, pp. 251-263.
  5. F.Cicalese, F. Manne, and Q. Xin, Faster Centralized Communication in Radio Networks. Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), Springer LNCS 4288, pp. 339 -- 348.
  6. F. Manne and Q. Xin. Optimal Gossiping with Unit Size Messages in Known Radio Networks. Proceedings of the 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2006), Springer LNCS 4235, pp. 125 -134.
  7. F. Manne and M. Mjelde. A Memory Efficient Self-stabilizing Algorithm for Maximal k-packing. Eighth International Symposium on Stabilization, Safety, and Security of Distributed Systems, Springer LNCS 4271, pp. 428-439.
  8. H. Broersma, F. V. Fomin, J. Kratochvil, and G. J.Woeginger, Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult, Algorithmica 44 (4), (2006), pp. 343-361.
  9. F. Dorn, F. V. Fomin, and D. M. Thilikos. Fast subexponential algorithm for non-local problems on graphs of bounded genus. Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), Springer LNCS 4059, pp. 172-183.
  10. F. V. Fomin and K.H°ie, Pathwidth of cubic graphs and exact algorithms, Information Processing Letters, 97 (5), (2006), pp. 191-196.
  11. F. V. Fomin* and D. M.Thilikos, New upper bounds on the decomposability of planar graphs, Journal of Graph Theory, 51 (1), (2006), pp. 53-81
  12. D. Haugland and S.Stor°y. Local Search Methods for l1-Minimization in Frame Based Signal Compression. Optimization and Engineering, 7 (2006), pp.81-96.

2005:

  1. C.Paul and J.A.Telle Edge-maximal graphs of branchwidth k Proceedings ICGT'05, 7th International Colloquium on Graph Theory, Electronic Notes in Discrete Mathematics, vol 22, 363-368
  2. E.D. Demaine, F.V. Fomin, M.T. Hajiaghayi, and D.M. Thilikos, Fixed-parameter algorithms for the $(k,r)$-center in planar graphs and map graphs, ACM Transactions on Algorithms (TALG), 1(1), (2005), pp. 33--47.
  3. F. V. Fomin, F. Grandoni, and D. Kratsch. Measure and Conquer: Domination -- A Case Study. Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), LNCS, vol. 3580, 2005, pp. 191-203.
  4. F. Manne and E. Boman. Balanced greedy colorings of sparse random graphs. Proceedings of NIK05, The Norwegian Informatics Conference, pp.113-124, 2005.
  5. D. Bozdag, U. Catalyurek, A.H. Gebremedhin, F. Manne, E.G. Boman and F. Ozguner, A Parallel Distance-2 Graph Coloring Algorithm for Distributed Memory Computers. Proc. of HPCC 2005, Sept 21-25, 2005, Sorrento, Italy. Lecture Notes in Computer Science, Vol 3726, pages 796-806, 2005.
  6. E.G. Boman, D. Bozdag, U. Catalyurek, A.H. Gebremedhin and F. Manne. A Scalable Parallel Graph Coloring Algorithm for Distributed Memory Computers, Proc. of EuroPar 2005, Aug 30-Sept 2, 2005, Lisboa, Portugal. Lecture Notes in Computer Science, Vol 3648, pages 241-251, 2005.
  7. F. Fomin, P. Heggernes and D. Kratsch. Exact algorithms for graph homomorphisms Proceedings FCT 2005 - 15th International Symposium on Fundamentals of Computation Theory, LNCS 3623, pages 161 - 171, 2005.
  8. P. Heggernes and D. Lokshtanov. Optimal broadcast domination of arbitrary graphs in polynomial time Proceedings WG 2005 - 31st Workshop on Graph Theoretic Concepts in Computer Science, LNCS 3787, 187-198, 2005.
  9. J.Fiala, D.Paulusma and J.A.Telle. Matrix and graph orders derived from locally constrained graph homomorphism Proceedings MFCS'05, 30th International Symposium on Mathematical Foundations of Computer Science. LNCS 3618, 340-351, 2005.
  10. J.Fiala, D.Paulusma and J.A.Telle. Algorithms for comparability of matrices in partial orders imposed by graph homomorphisms Proceedings WG'05, 31st Workshop on Graph Theoretic Concepts in Computer Science. LNCS vol 3787, 115-226, 2005.
  11. A. Gebremedhin, F. Manne, and T. Woods. Speeding up parallel graph coloring. Proc. of Para 2004, June 20-23, 2004, Lyngby, Denmark. Lecture Notes in Computer Science, Vol 3732, pp. 1079 - 1088 2005.

2004:

  1. E.D. Demaine, F.V. Fomin, M.T. Hajiaghayi, and D.M. Thilikos, Bidimensional Parameters and Local Treewidth. SIAM Journal on Discrete Mathematics 18 (3), (2004), pp.501--511.
  2. J. Blair and F. Manne. Efficient Generic Multi-stage Self-stabilizing algorithms for trees. In Proc. 17th International Conference on Parallel and Distributed Computing Systems (PDCS04). San Francisco, USA, 2004, pp 333--338.
  3. J. Fiala, A.V. Fishkin, and F.V. Fomin, On Distance Constrained Labeling of Disk Graphs, Theoretical Computer Science 326 (1-3), (2004), pp. 261-292.
  4. H.L. Bodlaender, H. Broersma, F.V. Fomin, A.V. Pyatkin, and G. J. Woeginger, Radio labeling with preassigned frequencies, SIAM Journal on Optimization 15 (1), 2004, pp.1-16.
  5. F. V. Fomin, M. Matamala, E. Prisner, and I. Rapaport. AT-free graphs: linear bounds for the oriented diameter. Discrete Applied Mathematics 141 (1-3), (2004), pp. 135-148.
  6. F. V. Fomin, D. Kratsch, and G. J. Woeginger. Exact (exponential) algorithms for the dominating set problem. Proceedings of the 30th Workshop on Graph Theoretic Concepts in Computer Science (WG 2004), Springer LNCS vol. 3353, 2004, pp.245-256.
  7. H.L. Bodlaender and F.V. Fomin, Equitable colorings of bounded treewidth graphs, Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Springer-Verlag Lecture Notes in Computer Science, vol. 3153, 2004, pp.180-190.
  8. H. Broersma, F.V. Fomin, and G.J. Woeginger, Parallel knock-out schemes in networks, Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Springer-Verlag Lecture Notes in Computer Science, vol. 3153, 2004, pp.204-214.
  9. F.V. Fomin and D.M. Thilikos, Fast parameterized algorithms for graphs on surfaces, Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), Springer-Verlag Lecture Notes in Computer Science, vol. 3142, 2004, pp.581-592.
  10. F.V. Fomin and D.M. Thilikos, A Simple and Fast Approach for Solving Problems on Planar Graphs Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), Springer LNCS, vol. 2996, 2004, pp.56-67.
  11. F. V. Fomin, M. Matamala, and I. Rapaport. The complexity of approximating the oriented diameter of chordal graphs. J. Graph Theory 45 (4) (2004), pp. 255 - 269.
  12. E.D. Demaine, F.V. Fomin, M.T. Hajiaghayi, and D.M. Thilikos, Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 823-832.
  13. F. V. Fomin, D. Kratsch and H. Muller, Algorithms for graphs with small octopus Discrete Appl. Math. 134 (1-3) (2004), pp. 105-128.
  14. J.Blair, P.Heggernes, S.Horton, and F.Manne. Broadcast Domination Algorithms for Interval Graphs, Series-Parallel Graphs, and Trees. Congressus Numerantium,169 (2004), pp. 55-77.
  15. Project description . (PDF)